Jack H. Lutz, Elvira Mayordomo

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 ...
more >>>