An Oracle Strongly Separating Deterministic Time from Nondeterministic Time, via Kolmogorov Complexity
David Doty · arXiv (Cornell University) · 2010
Hartmanis used Kolmogorov complexity to provide an alternate proof of the classical result of Baker, Gill, and Solovay that there is an oracle relative to which P is not NP. We refine the technique to strengthen the result, constructing an oracle relative to which a conjecture of Lipton is false.