CS 7805。复杂性理论。(4小时)

在计算复杂度涵盖了核心主题,包括np完全,时间和空间复杂性,多项式层次结构,电路复杂性,概率计算,互动证明,硬度近似。移动到更高级的主题,可能包括下界,伪随机数,密码学,和沟通的复杂性。

先决条件:CS 7800最低等级的C -