PfNPf for almost all f

[bibtex key=HamkinsWelch2003:PfneqNPf]

Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines Pf=NPf can be true for any function f from the reals into ω1. We show that “almost everywhere” the answer is negative.

One thought on “PfNPf 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 *