Theory of Computation (V-U)

• Introduction (V-U)
• Turing Machine and its Language (V-U)
• Designing Turing Machines (V-U)
• Variants of Turing Machines (V-U)
• Enumerators, Dovetailing, The Church-Turing Thesis, Hilbert's Tenth Problem (V-U)
• Decidable Languages, The Acceptance Problem for DFAs (V-U)
• The Halting Problem, Universal TM (V-U)
• Undicidability of the Halting Problem (V-U)
• Linear Bounded Automata, Computation Histories, Context Free Grammars (V-U)
• Russell's Paradox, Emptiness Problem (V-U)
• Post Correspondence Problem, Computable Functions (V-U)
• Computable Functions (Cont.), Reducibility (V-U)
• Reducibility (Cont.), Recursion Theorem (V-U)
• Recursion Theorem (Cont.), Logical Theories (V-U)
• Logical Theories (Cont.) (V-U)
• Logical Theories (Cont.), Godel's Theorem (V-U)
• Oracles, Turing Reducibility (V-U)
• A definition of Information, Incompressible Strings (V-U)
• Incompressible Strings (Cont.), Complexity Theory (V-U)
• Big Oh and Little Oh Notations, Time Complexity (V-U)
• Non-Deterministic Time, The Class P, The Class NP (V-U)
• The Class NP (Cont.), Polynomial Time Verifiers (V-U)
• The Class NP (Cont.) (V-U)
• Subset Sum Problem, Satisfiability (V-U)
• Satisfiability (Cont.), 3-Color (V-U)