Abstract
We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines P-f = NPf can be true for any function f from the reals into w(1). We show that "almost everywhere" the answer is negative.
Translated title of the contribution | Pf does not equal NPf for almost all f |
---|---|
Original language | English |
Pages (from-to) | 536 - 540 |
Number of pages | 5 |
Journal | Mathematical Logic Quarterly |
Volume | 49 (5) |
DOIs | |
Publication status | Published - Sept 2003 |