On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines

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 ${\mathrm{P}}^{+},{\mathrm{NP}}^{+}$. Schindler showed that P $\ne$ NP and ${\mathrm{P}}^{+}\ne {\mathrm{NP}}^{+}$. We show that P $=$ NP $\cap$ co-NP and NP $\ne$ co-NP, whereas ${\mathrm{P}}^{+}\subset$ NP $\cap$ co-NP and ${\mathrm{NP}}^{+}\ne$ co-NP${}^{+}$.

9 pages