Presentation is loading. Please wait.

Presentation is loading. Please wait.

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.

Published byΚαλόγερος Κυπραίος Modified 5年之前

Similar presentations

Presentation on theme: "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."— Presentation transcript:

1 Boolean circuits 姚鹏晖助教: 刘明谋答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502

2 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.

3 Boolean circuits

4 Class P/poly

5 Class P/poly

6 Class P/poly

7 Circuit satisfiability

8 Uniformly generated circuits

9 Turing machines that take advice

10 Turing machines that take advice

Download ppt "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."

Similar presentations

To make this website work, we log user data and share it with processors. To use this website, you must agree to our Privacy Policy, including cookie policy.

Ads by Google