New Collapse Consequences of NP Having Small Circuits

DOI10.1137/S0097539795296206MaRDI QIDQ4210150zbMATHFDO

Authors Osamu Watanabe, Johannes Köbler

Publication date 21 September 1998

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

zbMATH Keywords

lower boundscomplexity classeslownesspolynomial-time hierarchyrandomized computationpolynomial-size circuitsself-reducible set

Mathematics Subject Classification ID

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)

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

(24)

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

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)