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 propertiesoraclecomparison of complexity classes

Mathematics Subject Classification ID

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

Related Items

A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Graph isomorphism is low for PP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Complexity results for structure-based causality. ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

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