Competing provers yield improved Karp-Lipton collapse results

DOI10.1016/j.ic.2005.01.002zbMath1066.68050OpenAlexW1996192734MaRDI QIDQ1775885

Jin-Yi Cai, Venkatesan T. Chakaravarthy, Hemaspaandra, Lane A., Ogihara, Mitsunori

Publication date: 4 May 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.01.002

zbMATH Keywords

Karp-Lipton theoremStructural complexityCompeting proversKämper-AFK theoremLownessNonuniform complexitySymmetric alternationYap's theorem

Mathematics Subject Classification ID

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

Related Items (15)

Manipulation complexity of same-system runoff elections ⋮ Clique Cover and Graph Separation ⋮ Parameterized complexity of Eulerian deletion problems ⋮ The consequences of eliminating NP solutions ⋮ Pseudo-deterministic Proofs ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ On cutwidth parameterized by vertex cover ⋮ The 1-versus-2 queries problem revisited ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Proof systems that take advice ⋮ Complexity classes of equivalence problems revisited ⋮ On the Kernelization Complexity of Colorful Motifs ⋮ Nondeterministic Instance Complexity and Proof Systems with Advice ⋮ Parameterized Complexity of Eulerian Deletion Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• If NP has polynomial-size circuits, then MA=AM
• Arithmetization: A new method in structural complexity theory
• Improving known solutions is hard
• Some consequences of non-uniform conditions on uniform classes
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• Strong nondeterministic polynomial-time reducibilities
• Complexity and structure
• The complexity of combinatorial problems with succinct input representation
• Complexity classes without machines: on complete languages for UP
• Robust reductions
• Strong and robustly strong polynomial-time reducibilities to sparse sets
• Logarithmic advice classes
• On hiding information from an oracle
• Symmetric alternation captures BPP
• A taxonomy of complexity classes of functions
• Locating \(P\)/poly optimally in the extended low hierarchy
• More on BPP and the polynomial-time hierarchy
• Functions computable with nonadaptive queries to NP
• Relativizing relativized computations
• Bounded queries, approximations, and the Boolean hierarchy
• Oracles and queries that are sufficient for exact learning
• Self-reducibility
• The polynomial-time hierarchy and sparse oracles
• Robustness of probabilistic computational complexity classes under definitional perturbations
• PP is as Hard as the Polynomial-Time Hierarchy
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Polynomial Time Enumeration Reducibility
• New Collapse Consequences of NP Having Small Circuits
• BANISHING ROBUST TURING COMPLETENESS
• Algebraic methods for interactive proof systems
• Complexity classes defined by counting quantifiers
• NONDETERMINISTICALLY SELECTIVE SETS
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• The complexity theory companion

This page was built for publication: Competing provers yield improved Karp-Lipton collapse results