-
J. D. Hamkins and P. D. Welch, “${\rm P}^f\neq {\rm NP}^f$ for almost all $f$,” Math.~Logic Q., vol. 49, iss. 5, p. 536–540, 2003.
[Bibtex]@ARTICLE{HamkinsWelch2003:PfneqNPf, AUTHOR = {Hamkins, Joel David and Welch, Philip D.}, TITLE = {{${\rm P}^f\neq {\rm NP}^f$} for almost all {$f$}}, JOURNAL = {Math.~Logic Q.}, FJOURNAL = {Mathematical Logic Quarterly}, VOLUME = {49}, YEAR = {2003}, NUMBER = {5}, PAGES = {536--540}, ISSN = {0942-5616}, MRCLASS = {03D65 (03D10 03E45 68Q05 68Q15)}, MRNUMBER = {1998405 (2004m:03163)}, MRREVIEWER = {Peter G.~Hinman}, DOI = {10.1002/malq.200310057}, URL = {http://jdh.hamkins.org/pf-npf/}, eprint = {math/0212046}, archivePrefix = {arXiv}, primaryClass = {math.LO}, }
Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines $P^f = NP^f$ can be true for any function $f$ from the reals into $\omega_1$. We show that “almost everywhere” the answer is negative.
Pingback: P not= NP intersect coNP for infinite time Turing machines | Joel David Hamkins