On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines
Vinay Deolalikar · arXiv (Cornell University) · 2003
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 $ eq$ NP and ${\rm P}^+ eq {\rm NP}^+$. We show that P $=$ NP $\cap$ co-NP and NP $ eq$ co-NP, whereas ${\rm P}^+ \subset$ NP $\cap$ co-NP and ${\rm NP}^+ eq $ co-NP$^+$.