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.
Type de document :
Communication dans un congrès
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

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455362
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 11:19:00
Dernière modification le : lundi 29 janvier 2018 - 17:22:54
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:54:13

Fichier

fortnow.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

124

Téléchargements de fichiers

39