New Collapse Consequences of NP Having Small Circuits
DOI10.1137/S0097539795296206zbMATH Open0920.03052MaRDI QIDQ4210150FDOQ4210150
Authors: Osamu Watanabe, Johannes Köbler 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- New collapse consequences of NP having small circuits
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Some new consequences of the hypothesis that P has fixed polynomial-size circuits
- The new complexity landscape around circuit minimization
- New insights on the (non-)hardness of circuit minimization and related problems
- scientific article; zbMATH DE number 7204388
- On the (non) NP-hardness of computing circuit complexity
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- The complexity of satisfiability of small depth circuits
- scientific article; zbMATH DE number 987472
lower boundscomplexity classeslownesspolynomial-time hierarchyrandomized computationpolynomial-size circuitsself-reducible set
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cited In (24)
- Title not available (Why is that?)
- On Pseudodeterministic Approximation Algorithms.
- Towards efficient universal planning: A randomized approach
- Proving SAT does not have small circuits with an application to the two queries problem
- Complexity classes of equivalence problems revisited
- Title not available (Why is that?)
- New collapse consequences of NP having small circuits
- The power of natural properties as oracles
- Average-case intractability vs. worst-case intractability
- On bounded-probability operators and C\(_ =\)P
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- The shrinking property for NP and coNP
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Circuit lower bounds from learning-theoretic approaches
- Reducing the number of solutions of NP functions
- Arthur and Merlin as oracles
- Competing provers yield improved Karp-Lipton collapse results
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- On hard instances
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- On the limit of some algorithmic approach to circuit lower bounds
- Some structural properties of SAT
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
This page was built for publication: New Collapse Consequences of NP Having Small Circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210150)
