Pf does not equal NPf for almost all f

JD Hamkins; PD Welch

doi:10.1002/malq.200310057

P^f does not equal NP^f for almost all ^f

JD Hamkins, PD Welch

Research output: Contribution to journal › Article (Academic Journal) › peer-review

11 Citations (Scopus)

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	https://doi.org/10.1002/malq.200310057
Publication status	Published - Sept 2003

Bibliographical note

Publisher: Wiley - V C H Verlag GmbH

Access to Document

10.1002/malq.200310057

http://www3.interscience.wiley.com/cgi-bin/fulltext/104543867/PDFSTART

Handle.net

Persistent link

Cite this

@article{9a34eaa2b22f4e7eadcbbc1dd790bb81,

title = "Pf does not equal NPf for almost all f",

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.",

author = "JD Hamkins and PD Welch",

note = "Publisher: Wiley - V C H Verlag GmbH",

year = "2003",

month = sep,

doi = "10.1002/malq.200310057",

language = "English",

volume = "49 (5)",

pages = "536 -- 540",

journal = "Mathematical Logic Quarterly",

issn = "1521-3870",

publisher = "Wiley-VCH Verlag",

}

TY - JOUR

T1 - Pf does not equal NPf for almost all f

AU - Hamkins, JD

AU - Welch, PD

N1 - Publisher: Wiley - V C H Verlag GmbH

PY - 2003/9

Y1 - 2003/9

N2 - 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.

AB - 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.

U2 - 10.1002/malq.200310057

DO - 10.1002/malq.200310057

M3 - Article (Academic Journal)

SN - 1521-3870

VL - 49 (5)

SP - 536

EP - 540

JO - Mathematical Logic Quarterly

JF - Mathematical Logic Quarterly

ER -