CSCE-637 Complexity Theory

Delve into the intricate details of the Polynomial-Time Hierarchy, where complexity classes are defined based on the acceptance of languages by oracle Turing machines. Explore the hierarchy levels, such as PH=k^0, PH=k^0, and the distinctions between classes like P, NP, and co-NP. Gain insights into the computational cost spent on oracles and basic facts surrounding this fundamental concept in Complexity Theory.

• Complexity Theory
• Polynomial-Time Hierarchy
• Complexity Classes
• Oracle Turing Machine
• Computational Cost

wkam Follow

Uploaded on Mar 03, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. CSCE-637 Complexity Theory Fall 2020 Instructor: Jianer Chen Office: HRBB 338C Phone: 845-4259 Email: chen@cse.tamu.edu Notes 15: Polynomial-Time Hierarchy

2. Polynomial-Time Hierarchy Oracle Turing Machine MA: A TM M equipped with an oracle (i.e. a subroutine) that can (magically) answer the yes/no on the associate oracle language A work tape MA oracle tape for A

3. Polynomial-Time Hierarchy Definition. Let C be a complexity class. A language L is in PC (resp. NPC) if L is accepted by a deterministic (resp. nondeterministic) poly-time oracle TM MA, where A is a language in C. The computational cost spent on the oracle is not counted.

4. Polynomial-Time Hierarchy Definition. Let C be a complexity class. A language L is in PC (resp. NPC) if L is accepted by a deterministic (resp. nondeterministic) poly-time oracle TM MA, where A is a language in C. The computational cost spent on the oracle is not counted. Definition. ? = 0 for k 0 ? = P ?+1 ?+1 ? ? 3 3 ? ? 3 3 ? ? ? = 0 = P 0 3 ? 3 ? ? 2 2 ? ? 2 2 ? ? ? 2 ? ?+1 ? 2 ? ? = NP = co- ?+1 ? ? ? ? ?=coNP 1 1 NP= 1 1 ? ? ? P = 1 P = 1

5. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1

6. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ?

7. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ?

8. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 = co- ?+1 .

9. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 ?, ? = co- ?+1 ? ? . ?, ? ?, ? ? ?+1 ? . ?

10. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 ?, ? = co- ?+1 ? ? . ?, ? ?, ? ? ?+1 ? . ? ? = ?+1 ? ?(the poly-time hierarchy collapses) If ? , then PH = ?

11. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 ?, ? = co- ?+1 ? ? . ?, ? ?, ? ? ?+1 ? . ? ? = ?+1 ? ?(the poly-time hierarchy collapses) If ? , then PH = ? In particular, If P = NP, then PH = P.

12. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 ?, ? = co- ?+1 ? ? . ?, ? ?, ? ? ?+1 ? . ? ? = ?+1 ? ?(the poly-time hierarchy collapses) If ? , then PH = ? In particular, If P = NP, then PH = P. If PH has a complete problem (under poly-time reduction), then PH collapses.

13. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: 1 ? ? ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ? ? ? = P, ?+1 ?, ? = co- ?+1 ? ? . ?, ? ?, ? ? ?+1 ? . ? ? = ?+1 ? ?(the poly-time hierarchy collapses) If ? , then PH = ? In particular, If P = NP, then PH = P. If PH has a complete problem (under poly-time reduction), then PH collapses. It is commonly believed that PH does not collapse.

14. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 }

15. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 } Recall: NP: Co-NP: Q = { x | y|y| p(|x|) R(x, y) = 1 }, Q = { x | y|y| p(|x|) R(x, y) = 1 },

16. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 } ? = ? ?, then PH = ? ? If ?

17. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 } ? = ? ?, then PH = ? ? If ? Recall: ? = ?+1 ? ? If ? , then PH = ?

18. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 } ? = ? ?, then PH = ? ? If ? PSPACE-complete problem QBF: QBF = { x1 x2 Qxn F(x1, x2, , xn) = 1 }

19. Polynomial-Time Hierarchy Definition. 0 for k 0, ?+1 The polynomial-time hierarchy (PH) PH = k 0 ? Basic Facts: ? ? ? = 0 = 0 = P = P ? ? ? ? ? ? ? ? , ?+1 = NP , ?+1 = co- ?+1 ? = k 0 ? ?= k 0 ? ? ?: A = { x | py1 py2 Qpyk FA(x, y1, y2, , yk) = 1 } (QBFk) ? ? ?: B = { x | py1 py2 Qpyk FB(x, y1, y2, , yk) = 1 } ? = ? ?, then PH = ? ? If ? PSPACE-complete problem QBF: QBF = { x1 x2 Qxn F(x1, x2, , xn) = 1 } Thus, PH PSPACE.

20. Major Open Problems

21. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE

22. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE

23. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2

24. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2 P = NP?

25. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2 P = NP? NP = coNP?

26. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2 P = NP? NP = coNP? ? = ?+1 ? for some k? ? ? = ? ? for some k? ?

27. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2 P = NP? NP = coNP? ? = ?+1 ? for some k? ? } does the PH collapse? ? = ? ? for some k? ?

28. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE NP= 1 2 ? ? ? P ? 2 PH PSPACE 3 ? coNP= 1 ? 2 P = NP? NP = coNP? ? = ?+1 ? for some k? ? } does the PH collapse? ? = ? ? for some k? ? PH = PSPACE?

29. Major Open Problems NC1 L NL NC2 NC3 . NC P NP PSPACE 2 P coNP= 1 2 ? ? NP= 1 2 ? ? PH PSPACE 3 ? ? P = NP? NP = coNP? ? = ?+1 ? for some k? ? } does the PH collapse? ? = ? ? for some k? ? PH = PSPACE? We believe that the answers to all questions above are NO . Thus, any conjecture that implies an equality above is regarded as unlikely.