Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Wednesday, February 10, 2010 - 11:19:00 AM
Last modification on : Saturday, February 20, 2021 - 9:38:03 PM
Long-term archiving on: : Friday, June 18, 2010 - 7:54:13 PM


Files produced by the author(s)


  • HAL Id : inria-00455362, version 1



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⟩



Record views


Files downloads