Search Colleges, Exams, Schools & more
Login
Basics of Computational Complexity
Online
12 Weeks
Free Quick Facts
| Medium Of Instructions | Mode Of Learning | Mode Of Delivery |
|---|---|---|
| English | Self Study | Video and Text Based |
Courses and Certificate Fees
| Certificate Availability | Certificate Providing Authority |
|---|---|
| yes | IIT Kanpur |
The Syllabus
- Introduction
- Outline
- Formalize problems and machine
- Turing Machine
- Asymptotics, Church-Turing thesis, and UTM
- Halting problem and Diagonalization
- Classes P, NP, EXP
- Comparison of classes and Non-determinism
- NP vs Ntime
- SAT is NP-hard.
- Cook-Levin Theorem.
- NP-hardness and Co-Classes
- NEXP and Gödel'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 connection to the cycle cover of a Graph
- P-complete: Graph gadgets
- P-hard: Analyse XOR
- Valiant-Vazirani Lemma and Hashing
- SAT to Parity-SAT
- Parity Quantification
- Randomized reduction of PH to Parity-P
- PH to #P
- Probabilistic TM
- Example of PTM and Introduction to RP and ZPP
- ZPP = RP & coRP
- Probability Amplification
- BPP in PH
- GNI is in BP.NP
- GI is NP-hard.
- GI is NP-hard continued. Going Beyond TMs
- Circuit Complexity
- TM with Advice - P/poly.
- Circuits for NP and EXP
- Parallel Computation.
- P-completeness and NEXP-completeness