Polynomial Hierarchy 姚鹏晖

Presentation on theme: "Polynomial Hierarchy 姚鹏晖"— Presentation transcript:

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

2 What we have learnt The complexity PSPACE, L, NL
TQBF is PSPACE-complete Savitch’s theorem PSPACE=NPSPACE, PATH is NL-complete (logspace reduction) Immerman-Szelepcsényi Theorem: NL=coNL

3 Synthesizing circuits is exceedingly difficulty
Synthesizing circuits is exceedingly difficulty. It is even more difficult to show that a circuit founding this way is the most economical one to realize a function. The difficulty springs from the large number of essentially different networks available. – Claude Shannon, 1949

4 Class 𝚺 𝟐 𝒑

5 Polynomial hierarchy

6 Properties

7 𝚺 𝟐 𝒑 -complete problems

8 Alternate definitions

9 Alternate Turing machines

10 Alternate Turing machines

11 Alternate Turing machines

12 Alternate Turing machines

13 Alternate Turing machines

14 Alternate Turing machines

15 Alternate Turing machines

16 Time/space tradeoff

17 Time/space tradeoff

18 Time/space tradeoff

19 Homework 或放到计算机科学与技术楼502门口信封 (中英文不限)
Chapter 5. Exercise 5.2, 5.5, 5.6, 5.12 作业发送给助教刘明谋 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间：11月1日10:00前