scientific article; zbMATH DE number 1962842

zbMATH Open1035.68053MaRDI QIDQ4418679FDOQ4418679

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

Title of this publication is not available (Why is that?)

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

Mathematics Subject Classification ID

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

Cited In (6)

• On zero error algorithms having oracle access to one query
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• 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
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

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)