Competing provers yield improved Karp-Lipton collapse results
type: Item
instance of: scholarly article
title: Competing provers yield improved Karp-Lipton collapse results
zbMATH Open document ID: 1066.68050
author: Jin-Yi Cai
author: Venkatesan T. Chakaravarthy
author: Lane A. Hemaspaandra
author: Ogihara, Mitsunori
published in: Information and Computation
publication date: 2005-05-04T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2165063
zbMATH Keywords: Structural complexity
zbMATH Keywords: Competing provers
zbMATH Keywords: Nonuniform complexity
zbMATH Keywords: Symmetric alternation
zbMATH Keywords: Karp-Lipton theorem
zbMATH Keywords: Yap's theorem
zbMATH Keywords: Kämper-AFK theorem
zbMATH Keywords: Lowness
MaRDI profile type: Publication
full work available at URL: j.ic.2005.01.002
OpenAlex ID: W1996192734
cites work: On hiding information from an oracle
cites work: Q4281491
cites work: If NP has polynomial-size circuits, then MA=AM
cites work: Arithmetization: A new method in structural complexity theory
cites work: Self-reducibility
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Logarithmic advice classes
cites work: Oracles and queries that are sufficient for exact learning
cites work: Functions computable with nonadaptive queries to NP
cites work: Q4418679
cites work: Robust reductions
cites work: More on BPP and the polynomial-time hierarchy
cites work: Bounded queries, approximations, and the Boolean hierarchy
cites work: Strong and robustly strong polynomial-time reducibilities to sparse sets
cites work: Complexity classes without machines: on complete languages for UP
cites work: NONDETERMINISTICALLY SELECTIVE SETS
cites work: BANISHING ROBUST TURING COMPLETENESS
cites work: Computing Solutions Uniquely Collapses the Polynomial Hierarchy
cites work: The complexity theory companion
cites work: Q3929039
cites work: Relativizing relativized computations
cites work: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
cites work: On self-reducibility and weak P-selectivity
cites work: Locating \(P\)/poly optimally in the extended low hierarchy
cites work: New Collapse Consequences of NP Having Small Circuits
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: Algebraic methods for interactive proof systems
cites work: Q4298260
cites work: Improving known solutions is hard
cites work: Symmetric alternation captures BPP
cites work: A low and a high hierarchy within NP
cites work: Complexity and structure
cites work: Polynomial Time Enumeration Reducibility
cites work: A taxonomy of complexity classes of functions
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: Complexity classes defined by counting quantifiers
cites work: AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
cites work: The complexity of combinatorial problems with succinct input representation
cites work: Some consequences of non-uniform conditions on uniform classes
cites work: Robustness of probabilistic computational complexity classes under definitional perturbations
DOI: 10.1016/J.IC.2005.01.002
description: scientific article; zbMATH DE number 2165063