License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2471
URN: urn:nbn:de:0030-drops-24711
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2471/
Go to the corresponding LIPIcs Volume Portal

Fortnow, Lance ; Lutz, Jack H. ; Mayordomo, Elvira

Inseparability and Strong Hypotheses for Disjoint NP Pairs

pdf-format:
1001.FortnowLance.2471.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{fortnow_et_al:LIPIcs:2010:2471,
  author =	{Lance Fortnow and Jack H. Lutz and Elvira Mayordomo},
  title =	{{Inseparability and Strong Hypotheses for Disjoint NP Pairs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{395--404},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2471},
  URN =		{urn:nbn:de:0030-drops-24711},
  doi =		{10.4230/LIPIcs.STACS.2010.2471},
  annote =	{Keywords: Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure, Genericity}
}

Keywords: Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure, Genericity
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI