Pf ≠ NPf for almost all f
Joel David Hamkins, PHILIP D. WELCH · Mathematical logic quarterly · 2003
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.