New Collapse Consequences of NP Having Small Circuits

DOI10.1137/S0097539795296206MaRDI QIDQ4210150zbMATH OpenFDO

Authors Osamu Watanabe, Johannes Köbler

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539795296206

zbMATH Keywords

complexity classeslower boundslownesspolynomial-size circuitspolynomial-time hierarchyrandomized computationself-reducible set

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Cited in

(28)

• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• On bounded-probability operators and C\(_ =\)P
• On hard instances
• Some structural properties of SAT
• Reducing the number of solutions of NP functions
• Competing provers yield improved Karp-Lipton collapse results
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• Towards efficient universal planning: A randomized approach
• Proving SAT does not have small circuits with an application to the two queries problem
• Circuit lower bounds from learning-theoretic approaches
• On the limit of some algorithmic approach to circuit lower bounds
• scientific article; zbMATH DE number 987472 (Why is no real title available?)
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• scientific article; zbMATH DE number 1962842 (Why is no real title available?)
• New collapse consequences of NP having small circuits
• On Pseudodeterministic Approximation Algorithms.
• Relations and equivalences between circuit lower bounds and karp-lipton theorems
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Average-case intractability vs. worst-case intractability
• The power of natural properties as oracles
• The shrinking property for NP and coNP
• Arthur and Merlin as oracles
• If NP has polynomial-size circuits, then MA=AM
• Complexity classes of equivalence problems revisited
• Symmetric exponential time requires near-maximum circuit size
• Oblivious complexity classes revisited: lower bounds and hierarchies
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

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)