New collapse consequences of NP having small circuits

DOI10.1007/3-540-60084-1_74zbMATH Open1412.68067OpenAlexW1573868303MaRDI QIDQ4645178FDOQ4645178

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

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

zbMATH Keywords

proof systemhash familycomplexity classadvice functioncollapse consequence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• New Collapse Consequences of NP Having Small Circuits
• Consequences of the provability of NP ⊆ P/poly
• Title not available (Why is that?)
• On bounded-probability operators and C\(_ =\)P
• The shrinking property for NP and coNP
• Competing provers yield improved Karp-Lipton collapse results
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• On small generators

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)