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

DOI10.1093/LOGCOM/EXI022MaRDI QIDQ3374094zbMATH OpenOpenAlexFDO

Authors Vinay Deolalikar, Joel David Hamkins, Ralf 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

complexity theorydescriptive set theory

Mathematics Subject Classification ID

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

Abstract: Schindler recently addressed two versions of the question P $stackrel?=$ NP for Turing machines running in transfinite ordinal time. These versions differ in their definition of input length. The corresponding complexity classes are labelled P, NP and ${mP}^{+},{mNP}^{+}$. Schindler showed that P $eq$ NP and ${mP}^{+}eq{mNP}^{+}$. We show that P $=$ NP $cap$ co-NP and NP $eq$ co-NP, whereas ${mP}^{+}subset$ NP $cap$ co-NP and ${mNP}^{+}eq$ co-NP${}^{+}$.

Recommendations

• P NP for infinite time Turing machines
• P ≠ NP for all infinite Boolean algebras
• Infinite-time Turing machines and Borel reducibility
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• Pf ≠ NPf for almost all f
• Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• scientific article; zbMATH DE number 2163541
• New Computational Paradigms
• \(\text{NP}\not={co}\)-NP and models of arithmetic

Cited in

(14)

• Turing machines with atoms
• The semaphore codes attached to a Turing machine via resets and their various limits
• P NP for infinite time Turing machines
• Symmetry for transfinite computability
• Koepke machines and satisfiability for infinitary propositional languages
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Infinite-time Turing machines and Borel reducibility
• Pf ≠ NPf for almost all f
• Some observations on infinitary complexity
• Is P = PSPACE for Infinite Time Turing Machines?
• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• scientific article; zbMATH DE number 1759437 (Why is no real title available?)
• P ≠ NP for all infinite Boolean algebras
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

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

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