Pf ≠ NPf for almost all f

DOI10.1002/MALQ.200310057MaRDI QIDQ4434508zbMATH OpenOpenAlexFDO

Authors 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

deterministic versus nondeterministic computationinfinite time Turing machinesordinal bounded computationrecursion theory on real numbers

Mathematics Subject Classification ID

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

Recommendations

• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• P NP for infinite time Turing machines
• Infinite time Turing machines
• A Survey of Infinite Time Turing Machines
• scientific article; zbMATH DE number 1909830

Cited in

(9)

• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• P NP for infinite time Turing machines
• Some observations on infinitary complexity
• Koepke machines and satisfiability for infinitary propositional languages
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• P ≠ NP for all infinite Boolean algebras
• \(\text{P}\neq \text{NP}\) for the reals with various analytic functions
• Symmetry for transfinite computability
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4434508)