Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | |||
21cs422 [2021-11-29] – [Synopsis/Syllabus:] Martin Ziegler | 21cs422 [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/ |
- | * Example problems: Hamiltonian Circuit, | + | |
* 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}}, | IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, | ||
- | * polynomial-time | + | * polynomial-time |
- | * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability | + | * equivalent problems: Clique |
* Cook-Levin Theorem, Master Reduction | * Cook-Levin Theorem, Master Reduction | ||
* Bin Packing is NP-complete | * Bin Packing is NP-complete |