Learn · Basics of Computational Complexity

Lecture 10 of 49Week 3

Lecture 5(b): SAT is NP-hard.

Prof. Nitin Saxena · IIT Kanpur

Credits and licence

From
Basics of Computational Complexity, IIT Kanpur (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  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
  5. Lecture 3(a): Asymptotics, Church-Turing thesis, and UTM Video
  6. Lecture 3(b): Halting problem and Diagonalization Video
  7. Lecture 4(a); Classes P, NP, EXP Video
  8. Lecture 4(b): Comparison of classes and Non-determinism Video
  9. Lecture 5(a): NP vs Ntime Video
  10. Lecture 5(b): SAT is NP-hard. Video
  11. Lecture 6(a): Cook-Levin Theorem. Video
  12. Lecture 6(b): NP-hardness and Co-Classes Video
  13. Lecture 7(a): NEXP and Gödel's computation question Video
  14. Lecture 7(b): Time, Space hierarchy Video
  15. Lecture 8(a): NDTM hierarchy Video
  16. Lecture 8(b): Ladner's Theorem and Introduction to Oracles Video
  17. Lecture 9(a): Oracle and Relativizing proofs. Video
  18. Lecture 9(b): Non-relativizing P≠NP and Introduction to Space complexity Video
  19. Lecture 10(a): PSPACE completeness Video
  20. Lecture 10(b): QBF game and NSpace Video
  21. Lecture 11(a): NL complete Video
  22. Lecture 11(b): NL=coNL Video
  23. Lecture 12(a): Polynomial Hierarchy Video
  24. Lecture 12(b): PH Conjecture Video
  25. Lecture 13(a): PH-complete and Oracle TM Video
  26. Lecture 13(b): NP^NP and #SAT Video
  27. Lecture 14(a): Counting classes #P and PP Video
  28. Lecture 14(b): Permanent and its connection to the cycle cover of a Graph Video
  29. Lecture 15(a): #P-complete: Graph gadgets Video
  30. Lecture 15(b): #P-hard: Analyse XOR Video
  31. Lecture 16(a): Valiant-Vazirani Lemma and Hashing Video
  32. Lecture 16(b): SAT to Parity-SAT Video
  33. Lecture 17(a): Parity Quantification Video
  34. Lecture 17(b): Randomized reduction of PH to Parity-P Video
  35. Lecture 18(a): PH to #P Video
  36. Lecture 18(b): Probabilistic TM Video
  37. Lecture 19(a): Example of PTM and Introduction to RP and ZPP Video
  38. Lecture 19(b): ZPP = RP & coRP Video
  39. Lecture 20(a): Probability Amplification Video
  40. Lecture 20(b): BPP in PH Video
  41. Lecture 21(a): GNI is in BP.NP Video
  42. Lecture 21(b): GI is NP-hard. Video
  43. Lecture 22(a): GI is NP-hard continued. Going Beyond TMs Video
  44. Lecture 22(b): Circuit Complexity Video
  45. Lecture 23(a): TM with Advice - P/poly. Video
  46. Lecture 23(b): Circuits for NP and EXP Video
  47. Lecture 24(a): Parallel Computation. Video
  48. Lecture 24(b): P-completeness and NEXP-completeness Video
  49. Live Session 13-02-2024 Video