Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Last revisionBoth sides next revision | ||
| 21cs422 [2021-11-29] – [Synopsis/Syllabus:] Martin Ziegler | 21cs422 [2021-11-29] – [Synopsis/Syllabus:] Martin Ziegler | ||
|---|---|---|---|
| Line 43: | Line 43: | ||
| * Boolean formulas and Satisfiability | * Boolean formulas and Satisfiability | ||
| * nondeterministic WHILE+ programs | * nondeterministic WHILE+ programs | ||
| - | * (Time) Hierarchy Theorem: P≠EXP | + | * Time Hierarchy Theorem: P≠EXP |
| IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, | IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, | ||
| Line 49: | Line 49: | ||
| * equivalent problems Clique, Independent Set, Boolean Satisfiability, | * equivalent problems Clique, Independent Set, Boolean Satisfiability, | ||
| * Cook-Levin Theorem, Master Reduction | * Cook-Levin Theorem, Master Reduction | ||
| - | * Ladner' | + | * Bin Packing is NP-complete |
| + | * Scenarios for P/NP, Ladner' | ||
| V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, | V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, | ||