On the power of deterministic reductions to C=P

DOI10.1007/BF01202284zbMATH Open0776.68045MaRDI QIDQ4032933FDOQ4032933

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1543330
• On the relative power of reduction notions in arithmetic circuit complexity
• scientific article; zbMATH DE number 4119625
• Reductions, completeness and the hardness of approximability
• On the Amount of Nondeterminism and the Power of Verifying
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• On the complexity-relativized strong reducibilities
• Polynomial-time reducibilities and ``almost all oracle sets
• On the power of deterministic transitive closures

Cites Work

• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• scientific article; zbMATH DE number 17529 (Why is no real title available?)
• scientific article; zbMATH DE number 176508 (Why is no real title available?)
• A relationship between difference hierarchies and relativized polynomial hierarchies
• BPP and the polynomial hierarchy
• Bounded Query Classes
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• PP is closed under intersection
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The complexity of combinatorial problems with succinct input representation
• The strong exponential hierarchy collapses

Cited In (10)

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

This page was built for publication: On the power of deterministic reductions to C=P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032933)