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