P^f NP^f for almost all f

Mathematical Logic Quarterly 49 (5):536 (2003)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 94,678

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

P f_≠ NP _f_ for almost all _f.Joel David Hamkins & Philip D. Welch - 2003 - Mathematical Logic Quarterly 49 (5):536-540.
Pointwise complexity of the derivative of a computable function.Ethan McCarthy - 2021 - Archive for Mathematical Logic 60 (7):981-994.
Infinite Time Turing Machines With Only One Tape.D. E. Seabold & J. D. Hamkins - 2001 - Mathematical Logic Quarterly 47 (2):271-287.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
A Note on Strongly Almost Disjoint Families.Guozhen Shen - 2020 - Notre Dame Journal of Formal Logic 61 (2):227-231.
P ≠ NP for all infinite Boolean algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.


Added to PP

35 (#455,011)

6 months
17 (#204,240)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Joel David Hamkins
Oxford University

Citations of this work

No citations found.

Add more citations

References found in this work

Infinite time Turing machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.

Add more references