%0 Journal Article
%T Inseparability and Strong Hypotheses for Disjoint NP Pairs
%A Lance Fortnow
%A Jack H. Lutz
%A Elvira Mayordomo
%J Computer Science
%D 2009
%I arXiv
%X 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.
%U http://arxiv.org/abs/0902.2674v4