Pf ≠ NPf for almost all f

DOI10.1002/malq.200310057zbMath1043.03036OpenAlexW2059434270MaRDI QIDQ4434508

Joel David Hamkins, Philip D. Welch

Publication date: 10 November 2003

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310057

zbMATH Keywords

infinite time Turing machinesdeterministic versus nondeterministic computationordinal bounded computationrecursion theory on real numbers

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Higher-type and set recursion theory (03D65)

Related Items (2)

Symmetry for transfinite computability ⋮ Koepke machines and satisfiability for infinitary propositional languages

This page was built for publication: Pf ≠ NPf for almost all f