Inseparability and Strong Hypotheses for Disjoint NP Pairs

Authors Lance Fortnow, Jack H. Lutz, Elvira Mayordomo



PDF
Thumbnail PDF

File

LIPIcs.STACS.2010.2471.pdf
  • Filesize: 284 kB
  • 10 pages

Document Identifiers

Author Details

Lance Fortnow
Jack H. Lutz
Elvira Mayordomo

Cite As Get BibTex

Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 395-404, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010) https://doi.org/10.4230/LIPIcs.STACS.2010.2471

Abstract

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

Subject Classification

Keywords
  • Computational Complexity
  • Disjoint NP-pairs
  • Resource-Bounded Measure
  • Genericity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail