On the power of deterministic reductions to C=P
From MaRDI portal
Publication:4032933
DOI10.1007/BF01202284zbMATH Open0776.68045MaRDI QIDQ4032933FDOQ4032933
Authors: Frederic Green 
Publication date: 17 May 1993
Published in: Mathematical Systems Theory (Search for Journal in Brave)
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
- The complexity of combinatorial problems with succinct input representation
- BPP and the polynomial hierarchy
- Bounded Query Classes
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The Boolean Hierarchy I: Structural Properties
- The strong exponential hierarchy collapses
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- PP is closed under intersection
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Title not available (Why is that?)
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
