New collapse consequences of NP having small circuits

DOI10.1007/3-540-60084-1_74MaRDI QIDQ4645178zbMATHOpenAlexFDO

Authors Osamu Watanabe, Johannes Köbler

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_74

zbMATH Keywords

proof systemhash familycomplexity classadvice functioncollapse consequence

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• New Collapse Consequences of NP Having Small Circuits
• scientific article; zbMATH DE number 1962842
• Competing provers yield improved Karp-Lipton collapse results
• Consequences of the provability of NP ⊆ P/poly
• If NP has polynomial-size circuits, then MA=AM

Cites work

• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Arithmetization: A new method in structural complexity theory
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Circuit-size lower bounds and non-reducibility to sparse sets
• Complexity and structure
• Computation times of NP sets of different densities
• Computational Complexity of Probabilistic Turing Machines
• Locating \(P\)/poly optimally in the extended low hierarchy
• Non-deterministic exponential time has two-prover interactive protocols
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• On hiding information from an oracle
• On relativized exponential and probabilistic complexity classes
• On self-reducibility and weak P-selectivity
• On sparse hard sets for counting classes
• Oracles and queries that are sufficient for exact learning
• Queries and concept learning
• Random generation of combinatorial structures from a uniform distribution
• Relativized circuit complexity
• Robustness of probabilistic computational complexity classes under definitional perturbations
• Self-reducibility
• Self-reducible sets of small density
• Sets with small generalized Kolmogorov complexity
• Some consequences of non-uniform conditions on uniform classes
• Strong nondeterministic polynomial-time reducibilities
• The polynomial-time hierarchy and sparse oracles
• Universal classes of hash functions

Cited in

(10)

• The shrinking property for NP and coNP
• Competing provers yield improved Karp-Lipton collapse results
• On bounded-probability operators and C\(_ =\)P
• scientific article; zbMATH DE number 1962842 (Why is no real title available?)
• On small generators
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• Consequences of the provability of NP ⊆ P/poly
• New Collapse Consequences of NP Having Small Circuits
• Relations and equivalences between circuit lower bounds and karp-lipton theorems
• Some new consequences of the hypothesis that P has fixed polynomial-size 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 Q4645178)