New collapse consequences of NP having small circuits

DOI10.1007/3-540-60084-1_74MaRDI QIDQ4645178zbMATH OpenOpenAlexFDO

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

advice functioncollapse consequencecomplexity classhash familyproof system

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

• 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
• 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?)
• 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

(13)

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