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