New Collapse Consequences of NP Having Small Circuits
From MaRDI portal
Publication:4210150
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)
lower boundslownesspolynomial-time hierarchyrandomized computationcomplexity classespolynomial-size circuitsself-reducible set
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
