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

Categories

Keywords

Reprint years

DOI

10.1002/malq.200310057

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

External links

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

Through your library

My notes

Similar books and articles

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.
Separations et transferts dans la hierarchie polynomiale des groupes abeliens lifinis.Ménard Bourgade - 2001 - Mathematical Logic Quarterly 47 (4):493-502.
Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals.P. D. Welch - 2000 - Journal of Symbolic Logic 65 (3):1193-1203.
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.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
Eventually infinite time Turing machine degrees: Infinite time decidable reals.P. D. Welch - 2000 - Journal of Symbolic Logic 65 (3):1193-1203.
Almost everywhere domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.

Analytics

Added to PP
2013-12-01

Downloads
58 (#283,612)

6 months
14 (#200,929)

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