Inseparability and Strong Hypotheses for Disjoint NP Pairs

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455362
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:19:00 AM
Last modification on : Thursday, February 14, 2019 - 3:33:33 PM
Long-term archiving on : Friday, June 18, 2010 - 7:54:13 PM

File

fortnow.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455362, version 1

Collections

Citation

Lance Fortnow, Jack H. Lutz, Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.395-404. ⟨inria-00455362⟩

Share

Metrics

Record views

157

Files downloads

143