https://wiki.devclub.in/index.php?action=history&feed=atom&title=COL753 2026-04-09T07:49:53Z Revision history for this page on the wiki MediaWiki 1.45.1 https://wiki.devclub.in/index.php?title=COL753&diff=589&oldid=prev 2026-03-04T10:00:10Z

<p>Creating course page via bot</p> <p><b>New page</b></p><div>{{Infobox Course<br /> | code = COL753<br /> | name = Complexity Theory<br /> | credits = 3<br /> | credit_structure = 3-0-0<br /> | pre_requisites = COL352 OR Equivalent<br /> | overlaps = <br /> }}<br /> <br /> == COL753 : Complexity Theory ==<br /> Modeling computation (Finite state machines, Non-determinism, Turing machines, class P etc.), NP and NP-completeness, Diagonalization (Time hierarchy and Ladner&#039;s theorem), Space complexity (PSPACE, NL, Savitch&#039;s theorem, Immerman-Szelepcsényi theorem etc.), Polynomial hierarchy, Boolean circuits (P/poly), Randomized classes (RP, BPP, ZPP, Adleman&#039;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&#039;s switching lemma), Other topics (#P, Toda&#039;s theorem, Average- case complexity, derandomization, pseudorandom construction).</div>

Prashantt492