Learn · NPTEL

Course10610435749 lectures

Basics of Computational Complexity

Prof. Nitin Saxena · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

Week 1

  1. Lecture 1(a): Introduction Video
  2. Lecture 1(b): Outline Video
  3. Lecture 2(a): Formalize problems and machine Video
  4. Lecture 2(b): Turing Machine Video

Week 2

  1. Lecture 3(a): Asymptotics, Church-Turing thesis, and UTM Video
  2. Lecture 3(b): Halting problem and Diagonalization Video
  3. Lecture 4(a); Classes P, NP, EXP Video
  4. Lecture 4(b): Comparison of classes and Non-determinism Video

Week 3

  1. Lecture 5(a): NP vs Ntime Video
  2. Lecture 5(b): SAT is NP-hard. Video
  3. Lecture 6(a): Cook-Levin Theorem. Video
  4. Lecture 6(b): NP-hardness and Co-Classes Video

Week 4

  1. Lecture 7(a): NEXP and Gödel's computation question Video
  2. Lecture 7(b): Time, Space hierarchy Video
  3. Lecture 8(a): NDTM hierarchy Video
  4. Lecture 8(b): Ladner's Theorem and Introduction to Oracles Video

Week 5

  1. Lecture 9(a): Oracle and Relativizing proofs. Video
  2. Lecture 9(b): Non-relativizing P≠NP and Introduction to Space complexity Video
  3. Lecture 10(a): PSPACE completeness Video
  4. Lecture 10(b): QBF game and NSpace Video

Week 6

  1. Lecture 11(a): NL complete Video
  2. Lecture 11(b): NL=coNL Video
  3. Lecture 12(a): Polynomial Hierarchy Video
  4. Lecture 12(b): PH Conjecture Video

Week 7

  1. Lecture 13(a): PH-complete and Oracle TM Video
  2. Lecture 13(b): NP^NP and #SAT Video
  3. Lecture 14(a): Counting classes #P and PP Video
  4. Lecture 14(b): Permanent and its connection to the cycle cover of a Graph Video

Week 8

  1. Lecture 15(a): #P-complete: Graph gadgets Video
  2. Lecture 15(b): #P-hard: Analyse XOR Video
  3. Lecture 16(a): Valiant-Vazirani Lemma and Hashing Video
  4. Lecture 16(b): SAT to Parity-SAT Video

Week 9

  1. Lecture 17(a): Parity Quantification Video
  2. Lecture 17(b): Randomized reduction of PH to Parity-P Video
  3. Lecture 18(a): PH to #P Video
  4. Lecture 18(b): Probabilistic TM Video

Week 10

  1. Lecture 19(a): Example of PTM and Introduction to RP and ZPP Video
  2. Lecture 19(b): ZPP = RP & coRP Video
  3. Lecture 20(a): Probability Amplification Video
  4. Lecture 20(b): BPP in PH Video

Week 11

  1. Lecture 21(a): GNI is in BP.NP Video
  2. Lecture 21(b): GI is NP-hard. Video
  3. Lecture 22(a): GI is NP-hard continued. Going Beyond TMs Video
  4. Lecture 22(b): Circuit Complexity Video

Week 12

  1. Lecture 23(a): TM with Advice - P/poly. Video
  2. Lecture 23(b): Circuits for NP and EXP Video
  3. Lecture 24(a): Parallel Computation. Video
  4. Lecture 24(b): P-completeness and NEXP-completeness Video

Live Session

  1. Live Session 13-02-2024 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Computer Science and Engineering
Teacher
Prof. Nitin Saxena
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed