- Meeting 20 : Thu, Sep 03, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Resource bounded computation. Resources required by Regular Languages and context free languages. Notion of complexity Measure. Blum's axioms.
- Meeting 21 : Fri, Sep 04, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Blum's axioms. Gap theorem. Speed up theorem. Time and Space constructible functions. Linear Speed up theorems.
References: | [K2] book. See the chapter on Abstract Complexity.
|
- Meeting 22 : Tue, Sep 08, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Linear Speed up theorems.
References: | Your class notes!!
|
- Meeting 23 : Thu, Sep 10, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Hierarchy theorems: Space hierarchy theorem, proof.
- Meeting 24 : Fri, Sep 11, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Time hierarchy theorem. Proof. First Lower bounds: Crossing sequence arguments.
- Meeting 25 : Sat, Sep 12, 09:00 am-12:00 pm
References | |
Exercises | |
Reading | |
First Lower bounds: Crossing sequence arguments. DSpace(o(loglog n))= DSpace(O(1)). The complexity classes EXP, E, and P, L (DLOG). Positioning of computational problems CLIQUE, SAT and REACH. CLIQUE is in EXP, SAT is in E, REACH is in P, DF-CONN is in L. EXACT-CLIQUE vs CLIQUE: efficient verifiability of solutions. Non-deterministic Turing machines. Non-deterministic Time and Space.
References: | Your class notes!!
|
- Meeting 26 : Mon, Sep 14, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Non-deterministic Time and Space. The classes NP and NL. CLIQUE and SAT are in NP.
References: | Your class notes!!
|
- Meeting 27 : Tue, Sep 15, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
CLIQUE is in NP. REACH is in NL.
References: | Your class notes!!
|
- Meeting 28 : Fri, Sep 18, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Relation to determinisitic counterparts: L subseteq NL subseteq P subseteq NP subseteq EXP. Characterization of classes: Notion of hardness and completeness.
- Meeting 29 : Mon, Sep 21, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Notions of reductions and completeness. log-space reductions. REACH is NL complete under log-space reductions.
- Meeting 30 : Mon, Sep 21, 05:00 pm-06:30 pm
References | |
Exercises | |
Reading | |
Closure properties of NL. Union, intersection and Complement. NL is closed under complement: Immermann-Szelepscenyi theorem.
References: | [MB Notes]. Also see [K2].
|
- Meeting 31 : Tue, Sep 22, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Time Complexity Classes, P, NP, EXP. Padding Arguments. P = NP implies NEXP = EXP. The class NP. Properties: closure under union and intersection. Boolean Circuits.
- Meeting 32 : Thu, Sep 24, 02:00 pm-03:45 pm
References | |
Exercises | |
Reading | |
Boolean circuits. Circuit Valuation Problem (CVP). CVP is P-Complete under log-space reductions. Circuit Satisfiability (CSAT). CSAT is NP-complete under log-space reductions.
- Meeting 33 : Fri, Sep 25, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
More NP complete problems: Vertex Cover, Clique. Landscape of complexity classes.
- Meeting 34 : Mon, Oct 19, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Ladner's theorem introduction and proof.
- Meeting 35 : Tue, Oct 20, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Ladner's theorem: proof
- Meeting 36 : Mon, Oct 26, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Generalizations of NP. 1) Based alternating quantifiers. Definition of Polynomial Hierarchy. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. 2) Characterization of PH in terms of relativizations.
References: | [MBNotes]
|
Reading: | There are several natural complete problems for various levels of PH. See a compendium of such problems maintained by Schaefer and Umans. |
- Meeting 37 : Tue, Oct 27, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Quantified Boolean Formulas. Completeness for PH and PSPACE.
- Meeting 38 : Thu, Oct 29, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
PSPACE completeness of QBF. Alternating Turing machines. Relations to PSPACE and PH.
- Meeting 39 : Fri, Oct 30, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Oracle TMs, Turing reduction. Diagonalization and its limitation against Relativization: Baker-Gill-Solovay theorem. Proof of Baker-Gill-Solovay.
- Meeting 40 : Mon, Nov 02, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Proof of Baker Gill Solovay (contd). Mahaney's theorem: Sparse sets cannot be NP complete unless P = NP, proof sketch.
References: | For BGS see [K2]. For Mahaney's theorem see [MB Notes]. Also see the notes by Jin Yi Cai for a simplified presentation.
|