ECCC-Report TR09-022https://eccc.weizmann.ac.il/report/2009/022Comments and Revisions published for TR09-022en-usWed, 23 Sep 2009 10:37:53 +0300
Revision 1
| Inseparability and Strong Hypotheses for Disjoint NP Pairs |
Lance Fortnow,
Jack H. Lutz,
Elvira Mayordomo
https://eccc.weizmann.ac.il/report/2009/022#revision1This 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.
Wed, 23 Sep 2009 10:37:53 +0300https://eccc.weizmann.ac.il/report/2009/022#revision1
Paper TR09-022
| Inseparability and Strong Hypotheses for Disjoint NP Pairs |
Jack H. Lutz,
Elvira Mayordomo
https://eccc.weizmann.ac.il/report/2009/022This 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.
Thu, 19 Mar 2009 17:48:12 +0200https://eccc.weizmann.ac.il/report/2009/022