Polynomial Hierarchy 姚鹏晖 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 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
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
Class 𝚺 𝟐 𝒑
Polynomial hierarchy
Properties
𝚺 𝟐 𝒑 -complete problems
Alternate definitions
Alternate Turing machines
Alternate Turing machines
Alternate Turing machines
Alternate Turing machines
Alternate Turing machines
Alternate Turing machines
Alternate Turing machines
Time/space tradeoff
Time/space tradeoff
Time/space tradeoff
Homework 或放到计算机科学与技术楼502门口信封 (中英文不限) Chapter 5. Exercise 5.2, 5.5, 5.6, 5.12 作业发送给助教刘明谋 liu.mingmou@smail.nju.edu.cn 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间:11月1日10:00前