On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines
| dc.creator | Deolalikar, Vinay | |
| dc.date | 2003-05-30 | |
| dc.date.accessioned | 2026-07-07T04:58:25Z | |
| dc.date.available | 2026-07-07T04:58:25Z | |
| dc.description | 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 ${\rm P}^+,{\rm NP}^+$. Schindler showed that P $\neq$ NP and ${\rm P}^+ \neq {\rm NP}^+$. We show that P $=$ NP $\cap$ co-NP and NP $\neq$ co-NP, whereas ${\rm P}^+ \subset$ NP $\cap$ co-NP and ${\rm NP}^+ \neq $ co-NP$^+$. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/math/0305445 | |
| dc.identifier | http://arxiv.org/abs/math/0305445 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67628 | |
| dc.subject | Logic | |
| dc.subject | 68Q15; 68Q17; 03E15 | |
| dc.title | On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines | |
| dc.type | text |