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

Posted on by

[bibtex key=HamkinsWelch2003:PfneqNPf]

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

Your email address will not be published. Required fields are marked *