\(P\neq NP\) for infinite time Turing machines

DOI10.1007/S00605-002-0545-5zbMath1029.68071arXivmath/0106087OpenAlexW2167784134MaRDI QIDQ1408507

Ralf-Dieter Schindler

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

zbMATH Keywords

infinite time Turing machines

Mathematics Subject Classification ID

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