# ${\rm P}^f\neq {\rm NP}^f$ for almost all $f$

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