
Lecture 38 of 48 · Basics of Computational Complexity
Nitin Saxena
Basics of Computational Complexity · 48 lectures
48 lectures
Introduction
Outline
Formalize Problems and Machines
Turing Machine
Asymptotics, Church-Turing Thesis and UTM
Halting Problem and Diagonalization
Classes P, NP, EXP
Comparison of Classes and Non-determination
NP Vs Ntime
SAT is NP-hard
Cook-Levin Theorem
NP-Hardness and Co-Classes
NEXP and Godel’s Computation Question
Time, Space Hierarchy
NDTM Hierarchy
Ladner’s Theorem and Introduction to Oracles
Oracle and Relativizing Proofs
Non Relativizing P=NP and Introduction to Space Complexity
PSpace Completeness
QBF Game and NSpace
NL Complete
NL = coNL
Polynomial Hierarchy
PH Conjecture
PH Complete and Oracle TM
NP^NP and #SAT
Counting Classes #P and PP
Permanent and its Cycle cover of a Graph
#P-Complete: Graph Gadgets
#P-Hard: Analyse XOR
Part A - Valient-Vazirani Lemma and Hashing
Part B - SAT to Parity-SAT
Part A - Parity Quantification
Part B - Randomized Reduction of PH to Parity-P
Part A - PH to #P
Part B - Probabilistic TM
Part A - Example of PTM and Introduction to RP and ZPP
Part B - ZPP = RP and coRP
Part A - Probability Amplification
Part B - BPP in PH
Part A - GNI is in BP.NP
Part B - GI is NP-hard
Part A - GI is NP-hard (Continued...) Going Beyond TMs
Part B - Circuit Complexity
Part A - TM with Advice - P/poly
Part B - Circuits for NP and EXP
Part A - Parallel Computation
Part B - P-completeness and NEXP-completeness