scientific article; zbMATH DE number 1962842

MaRDI QIDQ4418679zbMATHFDO

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

Publication date 11 August 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070535.htm

Mathematics Subject Classification ID

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

Recommendations

• Competing provers yield improved Karp-Lipton collapse results
• New Collapse Consequences of NP Having Small Circuits
• Consequences of the provability of NP ⊆ P/poly
• New collapse consequences of NP having small circuits
• A tight Karp-Lipton collapse result in bounded arithmetic

Cited in

(8)

• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• Competing provers yield improved Karp-Lipton collapse results
• On zero error algorithms having oracle access to one query
• Relations and equivalences between circuit lower bounds and karp-lipton theorems
• A tight Karp-Lipton collapse result in bounded arithmetic
• New collapse consequences of NP having small circuits

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4418679)