Hyper-polynomial hierarchies and the polynomial jump

DOI10.1016/S0304-3975(00)00193-6zbMath0983.68075OpenAlexW2012199887MaRDI QIDQ5958122

No author found.

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00193-6

zbMATH Keywords

polynomial hierarchyhyper-polynomial hierarchypolynomial jumpsequences of degrees

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• A low and a high hierarchy within NP
• On the relative complexity of hard problems for complexity classes without complete problems
• The polynomial-time hierarchy
• Zur Theorie der konstruktiven Wohlordnungen
• PP is as Hard as the Polynomial-Time Hierarchy
• A polynomial jump operator
• Alternation
• On the Structure of Polynomial Time Reducibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item