Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
21cs422 [2021-11-29] – [Synopsis/Syllabus:] Martin Ziegler21cs422 [2021-11-30] (current) – [Synopsis/Syllabus:] Martin Ziegler
Line 39: Line 39:
   * Complexity classes P, NP, PSPACE, EXP   * Complexity classes P, NP, PSPACE, EXP
   * and their inclusion relations   * and their inclusion relations
-  * Example problems: Euler Circuit, Edge Cover +  * Example problems: Euler/Hamiltonian Circuit, Edge/Vertex Cover
-  * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Integer Linear Programming+
   * Boolean formulas and Satisfiability   * Boolean formulas and Satisfiability
   * nondeterministic WHILE+ programs   * nondeterministic WHILE+ programs
Line 46: Line 45:
  
 IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}): IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}):
-  * polynomial-time reductions +  * polynomial-time reduction 
-  * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability+  * equivalent problems: Clique = Independent Set <= Boolean Satisfiability <= 3-Satisfiability <= Independent Set
   * Cook-Levin Theorem, Master Reduction   * Cook-Levin Theorem, Master Reduction
   * Bin Packing is NP-complete   * Bin Packing is NP-complete