COL753: Difference between revisions
| [checked revision] | [checked revision] |
Prashantt492 (talk | contribs) Creating course page via bot |
Bot: wrap bare course codes in wikilinks |
||
| Line 4: | Line 4: | ||
| credits = 3 | | credits = 3 | ||
| credit_structure = 3-0-0 | | credit_structure = 3-0-0 | ||
| pre_requisites = COL352 OR Equivalent | | pre_requisites = [[COL352]] OR Equivalent | ||
| overlaps = | | overlaps = | ||
}} | }} | ||
Latest revision as of 16:26, 14 April 2026
| COL753 | |
|---|---|
| Complexity Theory | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | COL352 OR Equivalent |
| Overlaps | |
COL753 : Complexity Theory
Modeling computation (Finite state machines, Non-determinism, Turing machines, class P etc.), NP and NP-completeness, Diagonalization (Time hierarchy and Ladner's theorem), Space complexity (PSPACE, NL, Savitch's theorem, Immerman-Szelepcsényi theorem etc.), Polynomial hierarchy, Boolean circuits (P/poly), Randomized classes (RP, BPP, ZPP, Adleman's Theorem, Gács-Sipser-Lautemann Theorem), Interactive proofs (Arthur-Merlin, IP=PSPACE), Cryptography (one-way functions, pseudorandom generators, zero knowledge), PCP theorem and hardness of approximation, Circuit lower bounds (Hastad's switching lemma), Other topics (#P, Toda's theorem, Average- case complexity, derandomization, pseudorandom construction).