Boolean circuits 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502 http://tcs.nju.edu.cn/wiki/index.php/Main_Page
What we have learnt Time complexity P, NP, EXP, NEXP and complete problems Space complexity L, NL, PSPACE and complete problems Polynomial Hierarchy PH, which is sandwiched between NP and PSPACE.
Boolean circuits
Class P/poly
Class P/poly
Class P/poly
Circuit satisfiability
Uniformly generated circuits
Turing machines that take advice
Turing machines that take advice