Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Boolean circuits
Tags: fromMath mathToDef automaticImplies complexity defToProb hasSeenConjDef computer_to_instruction equivalentHand mathToSee toProblem

Name: An \(n\)-input, single-output Boolean circuit
Definition: a labelled directed acyclic graph with \(n\) sources, one sink and fan-in at most 2.
Page: 107
Chapter: 6
Section: 1
Variables: \(n\in\mathbb N\).
Kind: Definition

Name: Source
Definition: A vertex without incoming edges.
Page: 107
Chapter: 6
Section: 1
Variables: \(C\) a circuit
Kind: Definition

Name: A sink
Definition: A vertex without outgoing edge.
Page: 107
Chapter: 6
Section: 1
Kind: Definition

Name: Gates
Definition: The vertices with incoming and outgoing edges.
Page: 107
Chapter: 6
Section: 1
Kind: Definition

Name: The size of \(C\)
Definition: The number of vertices of \(C\).
Page: 107
Chapter: 6
Section: 1
Variables: \(C\) be a circuit.
Kind: Definition

Name: The value of \(v\)
Definition: \(x_i\) if \(i\) is the \(i\)-th input. And the label applied to its input edges otherwise.
Page: 107
Chapter: 6
Section: 1
Variables: \(C\) be a circuit and \(v\) a vertex of \(C\).
Context: Circuit
Notation: \(val(v)\)
Kind: Definition

Name: A \(T(n)\)-size circuit family
Definition: a sequence \(\{C_n\}_{n\in\mathbb N}\) of boolean circuits, where \(C_n\) has \(n\) inputs and a single output, and its size \(|C_n|\le T(n)\) for every \(n\).
Page: 108
Chapter: 6
Section: 1
Variables: \(T:\mathbb N\to \mathbb N\) be a function.
Index: 2
Kind: Definition

Question: The language \(\{1^n:n\in\mathbb Z\}\) can be decided by a circuit family which is
Answer: linear-sized
Page: 108
Chapter: 6
Section: 1
Index: 3
Kind: Ex

Question: The language \(\{\langle m,n,m+n\rangle:n,m\in\mathbb Z\}\) can be decided by
Answer: a linear-sized circuit family.
Page: 108
Chapter: 6
Section: 1
Index: 3
Kind: Ex

Question: Each function \(f:\{0,1\}^n\to\{0,1\}\) can be computed by
Answer: a circuit family of size \(O(2^n/n)\).
Page: 108
Chapter: 6
Section: 1
Kind: Ex

Name: A Straight-line program
Definition: A sequence of assignations of variables, using precedingly defined variables, boolean operation and inputs.
Page: 109
Chapter: 6
Section: 1
Index: 4
Kind: Note

Smaller0: \(\mathbf P\)
Greater0: the circuit is computed in PTIME and log-space
Page: 109
Chapter: 6
Section: 1.1
Kind: Theorem
Smaller to greater: \(\subsetneq\)
Prefix Greater: \(\mathbf P_{/poly}\) where
Greater to smaller: \(\supsetneq\)
Extra: Rem 7,8

Name: A unary language
Definition: A subset of \(1^*\).
Page: 109
Chapter: 6
Section: 1.1
Kind: Theorem

Page: 111
Section: 1.2
Chapter: 6
Name: Satisfiability of boolean circuit.
Time complexity: NP-complete
Kind: Lemma, Lem, Def
Index: 10, 11, 9
Language: typescript
Abbreviation: CKT-SAT

Name: A \(\pmb P\)-uniform family of circuits.
Definition: A family of circuits such that there is a polynomial time TM that on input \(1^n\) outputs the description of the circuit \(C_n\).
Page: 111
Chapter: 6
Section: 2
Index: 12
Kind: Definition

Question: A language has logspace-uniform circuits of poly size iff
Answer: it is in \(\pmb P\).
Page: 112
Chapter: 6
Section: 2.1
Index: 15
Kind: Theorem

Name: Languages decidable by time \(T(n)\) TM with \(a(n)\) bits of advice
Definition: Every \(L\) such that there exists a sequence \(\{\alpha_n\}_{n\in\mathbb N}\) of strings with \(\alpha_n\in\{0,1\}^{a(n)}\), and a TM \(M\) satisfying \(M(x,\alpha_n)=1\) if and only if \(x\in L\), for every \(x\) of length \(n\), where \(M\) runs in time \(T(n)\).
Page: 112
Chapter: 6
Section: 3
Variables: \(T,a:\mathbb N\to\mathbb N\).
Notation: \(\pmb {DTIME}(T(n))/a(n)\)
Index: 16
Kind: Definition

Question: \(\pmb{NP}\subseteq\pmb{P_{/\text{poly} } }\) implies
Answer: \(\pmb{PH}=\Sigma_2^p\).
Page: 113
Chapter: 6
Section: 4
Index: 19
Kind: Theorem

Smaller0: \(\pmb{EXP}\subseteq\pmb{P_{/\text{poly} } }\)
Greater0: \(\pmb{EXP}=\Sigma_2^p\)
Page: 114
Chapter: 6
Index: 20
Kind: Theorem

Question: There exists a function \(f:\{0,1\}^n\to\{0,1\}\) that cannot be computed by a circuit of size
Answer: \(2^n/10\).
Page: 115
Chapter: 6
Section: 5
Variables: \(n>1\).
Index: 21
Kind: Theorem

Smaller0: \(2^n/n>T'(n)>10T(n)>n\)
Greater0: \(SIZE(T(n))\subsetneq SIZE(T'(n))\)
Page: 116
Chapter: 6
Variables: \(T,T':\mathbb N\to\mathbb N\).
Index: 22
Kind: Theorem

Question: Addition can be parallelly computed in
Answer: log time with linear number of processor.
Page: 117
Chapter: 6
Section: 7
Index: 23
Kind: Ex

Definition: The set of languages \(L\) which can be decided by a family of circuits \(\{C_n\}\) with polynomial number of circuit and \(O(\log^d(n))\) depth.
Page: 117
Chapter: 6
Section: 7.1
Variables: \(d\in\mathbb N\)
\(L\) a language.
Notation: \(\pmb{NC}^d\)
Index: 24
Kind: Definition

Name: A language in uniform-\(\pmb{NC}^d\)
Definition: A language \(L\) which can be decided by a family of circuits \(\{C_n\}\), computable in log-space, with polynomial number of circuit and \(O(\log^d(n))\) depth.
Page: 117
Chapter: 6
Section: 7.1
Variables: \(d\in\mathbb N\)
\(L\) a language.
Index: 24
Kind: Definition

Name: \(\pmb{AC}^d\)
Definition: The set of languages which can be decided by a family of circuits \(\{C_n\}\), with polynomial number of gates, \(O(\log^d(n))\) depth and unbounded fan-in.
Page: 118
Chapter: 6
Section: 7.1
Variables: \(d\in\mathbb N\)
\(L\) a language.
Index: 25
Kind: Definition

Smaller0: \(\pmb{AC}^i\)
Greater0: \(\pmb{NC}^{i+1} \)
Page: 118
Chapter: 6
Section: 7.1
Variables: \(i\in\mathbb N\).
Smaller to greater: \(\subseteq\)
Hide middle: yes
Greater to smaller: \(\supseteq\)

Smaller0: \(\pmb{NC}^i\)
Greater0: \(\pmb{AC}^{i} \)
Page: 118
Chapter: 6
Section: 7.1
Variables: \(i\in\mathbb N\).
Smaller to greater: \(\subseteq\)
Hide middle: yes
Greater to smaller: \(\supseteq\)

Name: A language which admits an efficient parallel algorithm
Definition: A language which can be solved for inputs of size \(n\) using a parallel computer with \(n^{O(1)}\) processors in time \(\log^{O(1)}(n)\).
Page: 117
Chapter: 6
Section: 7
Variables: \(L\) a language.

Q: The language [...] is [...]
A: PARITY; \(\{x:x \text{ has an odd number of $1$s}\}\).
Page: 118
Chapter: 6
Section: 7
Index: 26
Kind: ex

Smaller0: PARITY
Greater0: \(\pmb{NC}^1\setminus\pmb{AC}^0\)
Page: 118
Chapter: 6
Section: 7
Index: 26
Kind: ex
Smaller to greater: belongs to the circuit class
Hide middle: yes
Greater to smaller: contains
Prefix Smaller: The language

Smaller0: has efficient parallel algorithm
Greater0: \(L\) belongs to \(\pmb{NC}\) characterization
Page: 118
Chapter: 6
Section: 7
Variables: \(L\) a language.
Index: 27
Kind: Theorem
Smaller to greater: iff
Hide middle: yes
Prefix Smaller: \(L\)

Name: \(\pmb P\)-hard language
Definition: A language such that every language in \(\pmb P\) is logspace-reducible to it.
Page: 119
Chapter: 6
Section: 7.2
Index: 28
Kind: Definition

Name: \(\pmb P\)-complete language
Definition: A language which is \(\pmb P\) and \(\pmb P\)-hard.
Page: 119
Chapter: 6
Section: 7.2
Index: 28
Kind: Definition

Smaller0: \(L\) is \(\pmb P\)-complete
Greater0: \(\pmb P=\pmb{NC}\)
Page: 119
Chapter: 6
Section: 7.2
Variables: \(L\) be a language.
Index: 29
Kind: Theorem
Smaller to greater: iff
Hide middle: yes
Smaller1: \(L\in \pmb{NC}\)
Prefix Smaller: If
Connect Smaller0: , then

Smaller0: \(L\) is \(\pmb P\)-complete
Greater0: \(\pmb{P=L}\)
Page: 119
Chapter: 6
Section: 7.2
Variables: \(L\) be a language.
Index: 29
Kind: Theorem
Smaller to greater: iff
Hide middle: yes
Smaller1: \(L\in\pmb L\)
Prefix Smaller: If
Connect Smaller0: , then

Page: 119
Section: 7.2
Chapter: 6
Name: Circuit-EVAL
Time complexity: \(\pmb P\)-complete language.
Returns: Whether \(C(x)=1\).
Input: A pair \(\langle C,x\rangle\) where \(C\) is a circuit and \(x\) an input
Kind: Theorem
Index: 30
Language: typescript

Name: A Direct Connect uniform family
Definition: \(\{\mathcal C_n\}_{n\ge1}\) a circuit family such that there is a polynomial-time algo that, given \(\langle n,i\rangle\) can compute in polynomial time the \(i\)th bit of the circuit \(C_n\).
Page: 119
Chapter: 6
Section: 8
Index: 31
Kind: Definition
Definition2: the functions SIZE, TYPE and EDGE are computable in P-time

Definition: The class of languages that are decidable by polynomial-sized circuits families.
Page: 108
Chapter: 6
Section: 1
Notation: \(\mathbf P/_{poly}\)
Index: 5
Kind: Definition
Definition2: \(\bigcup_{c}SIZE(n^c)\)
Extra: NC ?

Smaller0: \(L\) is unary
Greater0: \(L\) belongs to \(\pmb P_{/poly}\)
Page: 109
Chapter: 6
Section: 1.1
Variables: \(L\) a language.
Kind: Theorem
Hide middle: yes
Greater1: \(L\) belongs to \(\pmb DTIME(1)/1\)
Connect Greater0: and
Extra: 6.3 Ex 17

Smaller0: \(L\in\pmb{PH}\)
Greater0: \(L\) is accepted by a DC uniform family of circuit of size \(2^{n^{O(1)} }\) and constant depth, with unbounded fan-in, and Not only on gates
Page: 119
Chapter: 6
Section: 8
Variables: \(L\) be a language.
Index: 32
Kind: Theorem
Smaller to greater: iff
Hide middle: yes