Title: Theory / Unimportant / CS / Fundamental / Complexity / Descriptive complexity+14 / Parallelism
Tags: fromMath mathToDef mathToSee

\(t\) is polynomially bounded and first order constructible implies \[AC[t(n)]=IND[t(n)]=CRAM[t(n)]=ITER[t(n)]=FO[t(n)].\]
Page: 66, 71, 82, 160, 161
Chapter: 5
Section: 4
Variables: \(t:\mathbb N\to\mathbb N\)
Index: 25, 2, 22, 10, 13
Kind: Lem, Theo, Ex, Theo

Q: \([...]\subseteq [...]\subseteq [...]\).
A: CRAM-PROC[t(n), n^p]; IND-VAR[t(n),2p+2]; CRAM-PROC[t(n),n^{2p+2}]
Page: 75
Chapter: 5
Section: 3
Variables: \(t:\mathbb N\to\mathbb N\), \(p\in\mathbb N\).
Index: 10
Kind: Cor

Name: The vocabulary of circuit
Definition: \(\langle E^2,G^1_\land,G_\lor^1, G_\neg^1, I^1,r \rangle\)
Page: 79
Chapter: 5
Section: 4
Notation: \(\tau_c\)

Name: The vocabulary of Thresold circuit
Definition: \(T_c\cup\{G_t^2\}\).
Page: 79
Chapter: 5
Section: 4
Notation: \(\tau_{thc}\)
Index: 16
Kind: Def

Name: the dual of \(F\)
Variables: For \(F\) a linear formula
Notation: \(F^\bot\)

Smaller0: \(I\in FO[\sigma]\) (respectively, \(L\), \(P\))
Greater0: \(FO[\sigma]\)-uniform sequence of circuit (respectively, logspace-uniforme, polynomial-time uniform)
Page: 79
Chapter: 5
Section: 4
Variables: \(\mathcal C\) be a sequence of circuits, and \(\tau\) a vocabulary of circuit. Let \(I :STRUC[\tau_S]\to STRUC[\tau]\) be a query such that for all \(n\in\mathbb N\), \(I(0^n)=C_n\). That is, on input a string of \(n\) zero's the query produces circuit \(n\).
Index: 16
Kind: Def
Hide middle: yes
Prefix Greater: \(\mathcal C\) is
Suffix Smaller: ,

Q: [definition]
A: \(S\subseteq STRUC[\tau]\) be a boolean query such that there exists a (FO) query \(I:STRUC[\tau_s]\to STRUC[\tau_{thc}]\) defining a uniform class of circuits \(C_n=I(0^n)\) with the following properties:
- For all \(\mathcal A\in STRUC[\tau]\), \(\mathcal A\in S\iff C_{\parallel \mathcal A\parallel}\) accepts \(\mathcal A\).
- The depth of \(C_n\) is \(O(t(n))\)
- The gates of \(C_n\) consist of binary and and or gace (NC), unbounded fan-in and/or gates (AC) and unbounded fan-in threhold gates (ThC)
Page: 80
Chapter: 5
Section: 4
Variables: \(t(n):\mathbb N\to\mathbb N\) and let
Index: 17
Kind: Def
Name: (first-order uniform) circuit complexity class \(NC[t(n)]\), \(AC[t(n)]\), \(ThC[t(n)]\)

Name: \(NC^i\)
Definition: \(NC[(\log n)^i]\)
Page: 80
Chapter: 5
Section: 4
Index: 17
Kind: Def
Extra: Similarly for AC and ThC

Smaller0: \[NC\]
Greater0: \[\bigcup_iNC^i\]
Page: 80
Chapter: 5
Section: 4
Index: 17
Kind: Def
Smaller to greater: =
Hide middle: yes
Suffix Greater: and similarly for AC and ThC

Q: Every [...] is in [circuit]
A: regular language; \(NC^1\)
Page: 80
Chapter: 5
Section: 4
Index: 18
Kind: Def

Q: \[[...]=[...]=[\text{equivalence, not circuit classes}]\]
A: NC; \bigcup _kFO[(\log n)^k]; \bigcup _kCRAM[(\log n)^k]
Page: 84
Chapter: 5
Section: 4
Index: 26
Kind: Cor

Smaller0: \(DTIME[\log n]\)
Greater0: \(FO[+,\times]\)
Page: 85
Chapter: 5
Index: 30
Kind: Theo
Smaller to greater: is equivalent to
Hide middle: yes
Prefix Greater: the descriptive class
Prefix Smaller: the complexity class

Smaller0: \[NC[t(n)]\]
Greater0: \[ AC[t(n)/\log\log n]\]
Page: 88
Chapter: 5
Variables: \(t(n)>\log(n)\).
Index: 35
Kind: Theo
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Q: \([...]\subseteq [...]\subseteq [...]\)
A: AC[t(n)]; ThC[t(n)]; NC[t(n)\log (n)]
Page: 82
Chapter: 5
Variables: \(t:\mathbb N\to\mathbb N\).
Index: 22
Kind: Theo

Definition: Boolean queries computable in parallel time \(t(n)\) on a CRAM that has at most polynomially many processors.
Page: 70
Chapter: 13
Section: 1
Variables: \(t:\mathbb N\to\mathbb N\)
Notation: CRAM\([t(n)]\)

Definition: Boolean queries computable in parallel time \(t(n)\) on a CRAM that has at most \(p(n)\) processors on input of size \(n\).
Page: 70
Chapter: 13
Section: 1
Variables: \(p,t:\mathbb N\to\mathbb N\)
Notation: CRAM-PROC\([t(n),p(n)]\)

Name: Concurrent random access machine.
Page: 68
Chapter: 13
Section: 1
Abbreviation: CRAM