Playlist - Theory of computation

Introduction; course outline, mechanics, and expectations. Described finite automata, their formal definition, regular languages, regular operations, and regular expressions. Proved that the class of regular languages is closed under union. Started proving closure under concatenation.

Quickly reviewed last lecture. Introduced nondeterministic finite automata (NFA). Proved that NFA and DFA are equivalent in power. Proved that the class of regular languages is closed under concatenation and star. Showed conversion of regular expressions to NFAs.

Quickly reviewed last lecture. Showed conversion of DFAs to regular expressions. Gave a method for proving languages not regular by using the pumping lemma and closure properties. Introduced context free grammars (CFGs).

Quickly reviewed last lecture. Defined context free grammars (CFGs) and context free languages (CFLs). Defined pushdown automata (PDA). Gave conversion of CFGs to PDAs. Stated the reverse conversion without proof.

Quickly reviewed last lecture. Proved the CFL pumping lemma as a tool for showing that languages are not context free. Defined Turing machines (TMs). Defined TM deciders (halt on all inputs).

Quickly reviewed last lecture. Showed that various TM variants are all equivalent to the single-tape model. Discussed the Church-Turing Thesis: Turing machines are equivalent to “algorithms” and model-independence. Introduced notation for encoding objects and describing TMs.

Quickly reviewed last lecture. Showed the decidability of various problems about automata and grammars. Also showed that acceptance problem for TMs is T-recognizable.

Quickly reviewed last lecture. Showed that natural numbers and real numbers are not the same size to introduce the diagonalization method and used it to prove acceptance problem for TMs is undecidable. Introduced the reducibility method to show that HALT for TMs is undecidable.

Quickly reviewed last lecture. Discussed the reducibility method to prove undecidability and T-unrecognizability. Defined mapping reducibility as a type of reducibility. Showed that emptiness problem for TMs is undecidable and T-unrecognizable.

Quickly reviewed last lecture. Defined configurations and computation histories. Gave the computation history method to prove undecidability. Showed that acceptance problem for LBA is decidable; emptiness problem for LBA, PCP, and ALL for CFG are undecidable.

Quickly reviewed last lecture. Discussed self-reference and the recursion theorem. Gave various applications. Sketched Godel’s first incompleteness theorem in mathematical logic.

Quickly reviewed last lecture. Gave an introduction to complexity theory. Discussed limited complexity model-dependence for reasonable models. Defined TIME(t(n)) complexity classes and the class P. Showed that PATH is in P.

Quickly reviewed last lecture. Defined NTIME(t(n)) complexity classes and the class NP. Showed that COMPOSITES is in NP. Discussed the P versus NP question. Proved that acceptance problem for CFG is in P. Introduced the satisfiability problem SAT and polynomial-time reducibility.

Quickly reviewed last lecture. Covered NP-completeness; SAT and 3SAT; and more. Discussed a strategy for proving NP-completeness with a reduction from 3SAT by constructing gadgets that simulate variables and clauses.

Quickly reviewed last lecture. Proved Cook-Levin Theorem: SAT is NP-complete. Also proved 3SAT is NP-complete.

Quickly reviewed last lecture. Introduced space complexity. Defined SPACE(f(n)), NSPACE(f(n)), PSPACE, and NPSPACE. Proved that TQBF is in PSPACE; LADDER for DFA is in NSPACE(n); and LADDER for DFA is in SPACE(n²).

Quickly reviewed last lecture. Proved Savitch’s Theorem: NSPACE(f(n)) is a subset of SPACE(f ²(n)). Also proved PSPACE-completeness and TQBF is PSPACE-complete.

Quickly reviewed last lecture. Discussed a connection between games and quantifiers. Described the formula game and showed that generalized geography is PSPACE-complete. Introduced log space: L and NL. Defined the configuration graph to prove NL is a subset of P.

Reviewed log space: NL is a subset of SPACE(log²n) and NL is a subset of P. Introduced log-space transducers and log-space reducibility. Defined NL-completeness. Proved that PATH is NL-complete. Also proved the Immerman-Szelepcsényi theorem: NL = coNL.

Quickly reviewed last lecture. Finished Immerman-Szelepcsenyi theorem: NL = coNL. Introduced and proved the time and space hierarchy theorems. Discussed using the hierarchy theorems to separate certain complexity classes.

Quickly reviewed last lecture. Introduced exponential complexity classes and demonstrated a "natural" provably intractable problem. Introduced oracles and relativized computation to suggest that pure diagonalization-based methods cannot separate P and NP.

Quickly reviewed last lecture. Defined probabilistic Turing machines and the class BPP. Sketched the amplification lemma. Introduced branching programs and read-once branching programs. Started the proof that EQ for ROBP is in BPP. Introduced the arithmetization method.

Quickly reviewed last lecture. Simulated read-once branching programs by polynomials. Gave a probabilistic polynomial equality testing method. Concluded proving that EQ for ROBP is in BPP.

Quickly reviewed last lecture. Introduced the interactive proof system model. Defined the class IP. Started showing that #SAT is in IP to prove that coNP is a subset of IP.

Quickly reviewed last lecture. Discussed the arithmetization of Boolean formulas. Finished the theorem: #SAT is in IP and concluded that coNP is a subset of IP.