## 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 | P^{f} does not equal NP^{f} 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 - Sep 2003 |