Discrete

Regular

ATM
Halt-TM
Rice: Any non-trivial property of a language is undecidable
All-RE = {L: L is RE and L = Σ*} – decidable
All-CF = {L: L is CF and L = Σ*} – undecidable
- Construct CFG G: L(G) ≠ Σ* ⇔ M accepts w
- Run D on G; if it accepts, Reject; if it rejects; Accept
ECF = {(G, G’): G, G’ are CFGs, L(G) = L(G’)}
- Construct CFG G’, L(G’) = Σ*
- Run D(G, G’); contradicts the earlier result
Hilbert’s 10th problem

TIME(f(n)) = {L: L can be decided by a DTM in ≤ f(n) steps}
P
- P = ∪ TIME (n^c); Only ATM can be proved to be outside of P
- Poly-time reductions
  - 3SAT to CLIQUE
  - 3SAT to 3COLOR
  - 3SAT to SUBSET-SUM
NP
- NP = {L: w ∈ L ⇔ ∃ y, |y| ≤ |w|^c, M(w, y) = 1}
- P ⊆ NP – Proof: Ignore y
- Cook-Levin: 3SAT ∈ P ⇒ P = NP. (NPC)
- CLIQUE, SUBSET-SUM, 3COLOR ∈ NPC
EXP
- EXP = ∪ TIME (2^n^c)
- NP ∈ EXP
  - M’ = ∀ y, |y| ≤ |w|^c, check if M(w, y) = 1
  - M’ = 1 ⇔ L ∈ NP, and TIME(M’) = 2^n^c . |(w, y)|^c
- P ≠ EXP
  - Idea: Find an algo in EXP that is not in P
  - On i/p M, run M(M) for 2^n steps, n = |M|; return opposite of M
  - This is in TIME(n.2^n) which is in EXP
NEXP
Interactive Proof Systems
Zero-knowledge Proof System
- Anything in NP has a zero-knowledge proof!

Poly-time on TM = Poly-time on k-tape TM = Poly-time on RATM
- Write the contents of the k-th tape at the (k+i)-th position
- Write (addr, val) pairs from the RATM to TM
coNP = {L: L_bar ∈ NP}
NTIME(f(n)) = {L: L is decided by NTM in ≤ f(n) time}
NEXP = NTIME (2^poly(n))
P = NP ⇒ EXP = NEXP
- Use padding
- Choose a L ∈ NEXP; show that a DTM can decide L
NP requires ∃, coNP requires ∀
Some languages need both ∃ and ∀: Eg.: MIN-INDSET
Σ_i P = {L: x ∈ L ⇔ ∃ u₁ ∈ {0, 1}ⁿ ∀ u₂ ∈ {0, 1}^n … M (x, u₁, u₂, …, u_i) = 1}
- Σ₁ = NP
- Π₁ = coNP
PH = ∪ Σ_i = ∪ Π_i
P = NP ⇒ P = PH
- Proof by induction on i
  - Base case: i = 1: PH = Σ_i = NP = P (by assumption)
  - Inductive Hypothesis: Assume for i
  - Prove for (i + 1)
Π₂ ⊆ Σ₂ ⇒ PH = Σ₂

Boolean functions (OR, AND, NOT) form universal basis
- Any f: {0, 1}* –> {0, 1}, can be implemented
- Computable by O(2ⁿ) gates
  - TODO
Computable by s gates of fan-in h ⇒ computable by O(s) gates of fan-in 2
Computable with s gates ⇒ computable with s² wires: all pairs
Computable with s wires ⇒ computable with 0(s) wires: pairs
P/poly: poly-sized circuits
- ∃ f: f is undecidable but f ∈ P/poly
- if f ∈ TIME(t(n)), then ∀ n, f is computable by SIZE(t²⁽ⁿ⁾)
  - Encode tape symbols, state of TM using one encapsulated symbol
  - C yields C’; for each each symbol of C’, construct a O(1) size circuit to get this from the corresponding 3 symbols of C.
  - Pile t(n) copies of such circuits. Total size = O(t²⁽ⁿ⁾)
  - Corollary: P ⊆ P/poly
∃ c ∀ k, Σ_c is not computable by circuits in SIZE(n^k)
PH ⊆ EXP
∀ k, EXP is not computable by circuits in SIZE(n^k)
E = TIME(2^O(n))
E ⊆ P/poly ⇔ EXP ⊆ P/poly
NP ⊆ P/poly ⇔ PH = Σ₂
- TODO

SPACE(f(n)) = {L: L can be decided by DTM using space < f(n)}
NSPACE(f(n)) = {L: L can be decided by NTM using space < f(n)}
SPACE(s(n)) ⊆ TIME(2^O(s(n))), ∀ s(n) ≥ log(n)
- all possible configurations = n.2^O(s(n))
NSPACE(s(n)) ⊆ TIME(2^O(s(n))), ∀ s(n) ≥ log(n)
- Construct a configuration graph with nodes corresponding to 2^O(s(n)) states
- REACH(c_start, c_accept) which is O(2^O(s(n)))
TIME(t(n)) ⊆ SPACE(t(n)): you can only touch t(n) cells
L = SPACE(O(log n))
- Many basic functions: +, *, /, etc. are in L
NL = NSPACE((log n))
- Path ∈ NL
  - In the configuration graph, guess a neighbor, move there
- Path ∈ P ⇒ L = NL (NL-Complete)
  - Compute poly(|x|) config. graph of N on x. (since, 2^log(n)=n)
  - Accept ⇔ accept is reachable from start
  - if ∃ an algorithm for Path ∈ L, use that
PSPACE = SPACE(poly(n))
- QBF is PSPACE-complete # TODO
NPSPACE ⊆ PSPACE(poly(n)) ⇒ PSPACE = NPSPACE
- Savitch’s Theorem
  - REACH(c, c’, t)
  - if REACH(c, c’’, t/2) and REACH(c’’, c’, t/2) return YES
  - SPACE(REACH(t)) = O(s(n)) + SPACE(REACH(t/2))
  - Corollary: NL ⊆ SPACE(O(log²n))
NOT-PATH ∈ NL (⇒ coNL = NL)
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE
Space hierarchy: if f(n) = o(g(n)), then SPACE(f(n)) ⊆ SPACE(g(n))
- L ≠ PSPACE

RP = {L: poly-time random. TM M: x ∈ L ⇒ Pr[M(x, R)=1] ≥ 1/2, x ∉ L ⇒ Pr[M(x, R)=1] = 0}
- RP ⊆ NP
  - The witness is the random string
BPP = {L: poly-time random. TM M: x ∈ L ⇒ Pr[M(x, R)=1] ≥ 2/3, x ∉ L ⇒ Pr[M(x, R)=1] ≤ 1/3}
- BPP ⊆ P/poly
  - If L ∈ BPP, and M decides L
  - Error < 2^-n ⇒ ∀ x, Pr[L(x) ≠ M(x, R)] < 2^-n
  - By probabilistic method: ∃ R’ ∀ x: L(x) = M(x, R’).
  - Corresponding circuit made using R’ is in P/poly
- BPP ⊆ Σ₂
- BPP = coBPP
coRP = {L: L-bar in RP}
ZPP = {L: L ∈ RP ∩ coRP} (Zero-error machines: that never err)
P ⊆ ZPP ⊆ RP ⊆ BPP