On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines
Abstract
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$^+$.
9 pages
9 pages