Prefer a chat interface with context about you and your work?
Pf ≠ NPf for almost all f
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 ω 1 . We show that “almost everywhere” the answer is negative.