REPORTS > DETAIL:
Revision(s):
Revision #1 to TR09-022 | 23rd September 2009 10:37
Inseparability and Strong Hypotheses for Disjoint NP Pairs
Revision #1 Authors: Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
Accepted on: 23rd September 2009 10:37
Downloads: 163
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: 161
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.