Pf does not equal NPf for almost all f

JD Hamkins, PD Welch

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

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

Bibliographical note

Publisher: Wiley - V C H Verlag GmbH

Fingerprint

Dive into the research topics of 'P<sup>f</sup> does not equal NP<sup>f</sup> for almost all <sup>f</sup>'. Together they form a unique fingerprint.

Cite this