Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Fortnow, Lance; Lutz, Jack H.; Mayordomo, Elvira http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-24711
URL:

; ;

Inseparability and Strong Hypotheses for Disjoint NP Pairs

pdf-format:


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 =		{http://dx.doi.org/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
Seminar: 27th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2010
Date of publication: 2010


DROPS-Home | Fulltext Search | Imprint Published by LZI