Results

Chapter 2

Theorem 2.1 $P \subseteq NP \subseteq EXP$
Theorem 2.2 $NP = ⋃_{c \in N} NTIME (n^{c})$
Theorem 2.3(Cook-Levin Theorem) $SAT & 3 SAT$ are $NP$ -complete.
Hint: Snapshot expression
Theorem 2.4 $P = NP \Rightarrow decision = search for L \in NP$
Theorem 2.5 $P = NP \Rightarrow EXP = NEXP$
Hint: Padding

Theorem 3.1(Time Hierarchy Theorem) $f (n) \log f (n) = o (g (n)) \Rightarrow DTIME (f (n)) ⊈ DTIME (g (n))$
Hint: Time Limit+Diagonalization
Theorem 3.2(Nondeterministic Time Hierarchy Theorem) $f (n + 1) = o (g (n)) \Rightarrow NTIME (f (n)) ⊈ NTIME (g (n))$
Hint: Lazy Diagonalization
Theorem 3.3*(Ladner’s Theorem) $P \neq NP \Rightarrow NP - P \neq NPC$ P64
Oracle Machines (tbd)

Theorem 4.1 $DTIME (() s (n)) \subseteq SPACE (s (n)) \subseteq NSPACE (() s (n)) \subseteq DTIME (() 2^{O (s (n))})$ P72
Hint: Configuration Graph
Theorem 4.2(Space Hierarchy Theorem) $f (n) = o (g (n)) \Rightarrow SPACE (f (n)) ⊈ SPACE (g (n))$ P75
Theorem 4.3(Savitch’s Theorem) $s (n) > \log n$ , $NSPACE (s (n)) \subseteq SPACE (s^{2} (n))$ P77 Hint: Configuration Graph+Recursion

Theorem 5.1 $Σ_{i}^{p} = Π_{i}^{p} \Rightarrow PH = Σ_{i}^{p}$ P87
Theorem 5.2 $PH -complete \neq \emptyset \Rightarrow \exists i . PH = Σ_{i}^{p}$
Theorem 5.3 $AP = PSPACE$
Time Space Tradeoff (tbd)
Oracle Definition (tbd)

Theorem 6.1 $P \subseteq P_{/ p o l y}$
Theorem 6.2 $L$ is computable by a $P$ -uniform circuit family $\Leftrightarrow L \in P$
Theorem 6.3 $L$ is computable by a $L$ -uniform circuit family with polynomial size $\Leftrightarrow L \in P$
Theorem 6.4(TM with advice decides $P_{/ p o l y}$ ) $P_{/ p o l y} = ⋃_{c, d} DTIME (n^{c}) / n^{d}$
Hint: Consider Hardwiring the advice
Theorem 6.5(Karp-Lipton Theorem) $NP \subseteq P_{/ p o l y} \Rightarrow PH = Σ_{2}^{p}$
Hint: Circuit that outputs certificates
Theorem 6.6(Meyer’s Theorem) $EXP \subseteq P_{/ p o l y} \Rightarrow EXP = Σ_{2}^{p}$
Theorem 6.7(Hard Functions) $\exists f : {0, 1}^{n} \to {0, 1}$ not computable by circuit of size $\frac{2^{n}}{10 n}$
Hint: Probabilistic Method
Theorem 6.8(Non-uniform Hierarchy Theorem) $2^{n} / n > T^{'} (n) > 10 T (n) > 0 \Rightarrow SIZE (T (n)) ⊈ SIZE (T^{'} (n))$
P completeness (tbd)
Circuit of exponential size (tbd)

Theorem 7.1 $ZPP = RP \cap coRP$
Claim 7.2 $RP, coRP \subseteq BPP$
Theorem 7.3(Error Reduction) $\exists M . \underset{}{P} (M (x) = L (x)) \geq \frac{1}{2} + | x |^{- c} \Rightarrow \exists M^{'} . \underset{}{P} (M^{'} (x) = L (x)) \geq 1 - 2^{- | x |^{d}}$
Theorem 7.4 $BPP \subseteq P_{/ p o l y}$
Theorem 7.5(Sipser-Gács Theorem) $BPP \subseteq Σ_{2}^{p} \cap Π_{2}^{p}$ Hint: Translation of valid area