On the power of deterministic reductions to C=P

DOI10.1007/BF01202284zbMath0776.68045MaRDI QIDQ4032933

Frederic Green

Publication date: 17 May 1993

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

closure properties; oracle; comparison of complexity classes

Mathematics Subject Classification ID

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

Related Items

Generalized theorems on relationships among reducibility notions to certain complexity classes, A relationship between difference hierarchies and relativized polynomial hierarchies, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Graph isomorphism is low for PP, Complexity results for structure-based causality., Quantum and classical complexity classes: Separations, collapses, and closure properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• BPP and the polynomial hierarchy
• The complexity of combinatorial problems with succinct input representation
• PP is closed under intersection
• Bounded Query Classes
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A relationship between difference hierarchies and relativized polynomial hierarchies