P ≠ NP ∩ co-NP for Infinite Time Turing Machines

DOI10.1093/logcom/exi022zbMath1089.68043arXivmath/0305445OpenAlexW2149708996MaRDI QIDQ3374094

Joel David Hamkins, Vinay Deolalikar, Ralf-Dieter Schindler

Publication date: 9 March 2006

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0305445

zbMATH Keywords

descriptive set theorycomplexity theory

Mathematics Subject Classification ID

Descriptive set theory (03E15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Symmetry for transfinite computability ⋮ Infinite-Time Turing Machines and Borel Reducibility ⋮ Bounding lemmata for non-deterministic halting times of transfinite Turing machines ⋮ Koepke machines and satisfiability for infinitary propositional languages ⋮ Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems

This page was built for publication: P ≠ NP ∩ co-NP for Infinite Time Turing Machines