Pf does not equal NPf for almost all f

JD Hamkins, PD Welch

Research output: Contribution to journalArticle (Academic Journal)peer-review

11 Citations (Scopus)


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 contributionPf does not equal NPf for almost all f
Original languageEnglish
Pages (from-to)536 - 540
Number of pages5
JournalMathematical Logic Quarterly
Volume49 (5)
Publication statusPublished - Sept 2003

Bibliographical note

Publisher: Wiley - V C H Verlag GmbH


Dive into the research topics of 'Pf does not equal NPf for almost all f'. Together they form a unique fingerprint.

Cite this