Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Separable pairs:
TR09-022 | 16th February 2009
Jack H. Lutz, Elvira Mayordomo

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Revisions: 1

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

ISSN 1433-8092 | Imprint