P^f NP^f for almost all f

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

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

Links

PhilArchive



    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.

Analytics

Added to PP
2013-12-01

Downloads
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