Cryptology City
Search
Search
Dark mode
Light mode
Reader mode
Explorer
Cryptology City
Home
❯
Complexity
❯
Polynomial Hierarchy
Oct 04, 2026
Polynomial Hierarchy
See the complexity zoo entry
here
.
Notable problems
Known relationships
Graph View
Table of Contents
Polynomial Hierarchy
Notable problems
Known relationships
Backlinks
coNP ⊆ AM collapses the polynomial hierarchy
IP ⊆ AM collapses the polynomial hierarchy
No fully-black-box reduction from NP to cPIR
No reduction from NP to OWF
Arthur-Merlin
Co-Arthur-Merlin
P/poly