2010/04/22 by David Doty, Doty, David
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1004.3993
arxiv created 2010/04/22 · openalex publication_date 2010/04/22 · arxiv updated 2015/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.