Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-022 | 23rd September 2009 10:37

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Contact
Add Comment
RSS-Feed




Revision #1 Authors: Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
Accepted on: 23rd September 2009 10:37
Downloads: 4757
Keywords: 


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.



Changes to previous version:

We prove that three of these implications
cannot be reversed by relativizable techniques, and we conjecture that this
also holds for the remaining implication.


Paper:

TR09-022 | 16th February 2009 00:00

Inseparability and Strong Hypotheses for Disjoint NP Pairs





TR09-022 Authors: Jack H. Lutz, Elvira Mayordomo
Publication: 19th March 2009 17:48
Downloads: 3685
Keywords: 


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.


ISSN 1433-8092 | Imprint