Inseparability and Strong Hypotheses for Disjoint NP Pairs
Lance Fortnow, Jack H. Lutz, Elvira Mayordomo · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010
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.