Theory of Computation (V-U)

Logical Theories (Cont.), Godel's Theorem (V-U)

The Cook-Levin Theorem (V-U)

LOGSPACE Transducer (V-U)

The Halting Problem, Universal TM (V-U)

Non-Deterministic Time, The Class P, The Class NP (V-U)

The Subset Sum Problem (V-U)

NP-Completeness (Cont.) (V-U)

The Traveling Salesman Problem (V-U)

NP-Completeness, Independent Sets (V-U)

TQBF (Cont.), FORMULA-GAME, Generalized Geography (V-U)

Oracles, Turing Reducibility (V-U)

TQBF, Prove that TQBF is PSPACE-Complete (V-U)

Overview of the course covered

Turing Machine and its Language (V-U)

Post Correspondence Problem, Computable Functions (V-U)

Undicidability of the Halting Problem (V-U)

Prove the Theorem: NL = co-NL (Cont.) (V-U)

Variants of Turing Machines (V-U)

Prove the Theorem: NL = co-NL (V-U)

Recursion Theorem (Cont.), Logical Theories (V-U)