${\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$,” MLQ Math.~Log.~Q., vol. 49, iss. 5, pp. 536-540, 2003.  
    @ARTICLE{HamkinsWelch2003:PfneqNPf,
    AUTHOR = {Hamkins, Joel David and Welch, Philip D.},
    TITLE = {{${\rm P}^f\neq {\rm NP}^f$} for almost all {$f$}},
    JOURNAL = {MLQ Math.~Log.~Q.},
    FJOURNAL = {MLQ.~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://dx.doi.org/10.1002/malq.200310057},
    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.

One thought on “${\rm P}^f\neq {\rm NP}^f$ for almost all $f$

  1. Pingback: P not= NP intersect coNP for infinite time Turing machines | Joel David Hamkins

Leave a Reply