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

DOI10.1093/LOGCOM/EXI022zbMATH Open1089.68043arXivmath/0305445OpenAlexW2149708996MaRDI QIDQ3374094FDOQ3374094

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)

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${}^{+}$.

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

Recommendations

• \(P\neq 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

zbMATH Keywords

complexity theorydescriptive set theory

Mathematics Subject Classification ID

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

Cited In (11)

• \(P\neq 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
• Is P = PSPACE for Infinite Time Turing Machines?
• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• Title not available (Why is that?)
• 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)