New Collapse Consequences of NP Having Small Circuits

DOI10.1137/S0097539795296206zbMath0920.03052MaRDI QIDQ4210150

Osamu Watanabe, Johannes Köbler

Publication date: 21 September 1998

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

zbMATH Keywords

lower boundslownesspolynomial-time hierarchyrandomized computationcomplexity classespolynomial-size circuitsself-reducible set

Mathematics Subject Classification ID

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

Related Items (20)

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Average-case intractability vs. worst-case intractability ⋮ On the Limit of Some Algorithmic Approach to Circuit Lower Bounds ⋮ The power of natural properties as oracles ⋮ The shrinking property for NP and coNP ⋮ Arthur and Merlin as oracles ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Towards efficient universal planning: A randomized approach ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Complexity classes of equivalence problems revisited ⋮ Unnamed Item ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly ⋮ On hard instances ⋮ Some structural properties of SAT ⋮ Reducing the number of solutions of NP functions

This page was built for publication: New Collapse Consequences of NP Having Small Circuits