\(P\neq NP\) for infinite time Turing machines
From MaRDI portal
Publication:1408507
DOI10.1007/S00605-002-0545-5zbMath1029.68071arXivmath/0106087OpenAlexW2167784134MaRDI QIDQ1408507
Publication date: 23 September 2003
Published in: Monatshefte für Mathematik (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0106087
Descriptive set theory (03E15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
SAFE RECURSIVE SET FUNCTIONS ⋮ Symmetry for transfinite computability ⋮ Bounding lemmata for non-deterministic halting times of transfinite Turing machines ⋮ Koepke machines and satisfiability for infinitary propositional languages
This page was built for publication: \(P\neq NP\) for infinite time Turing machines