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
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.395-404, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455362
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:19:00 AM
Last modification on : Wednesday, February 10, 2010 - 11:26:57 AM
Document(s) archivé(s) le : 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. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.395-404, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455362>

Share

Metrics

Record views

118

Document downloads

35