# ${\rm P}\neq{\rm NP}\cap\textrm{co-}{\rm NP}$ for infinite time Turing machines

• V. Deolalikar, J. D. Hamkins, and R. Schindler, “${\rm P}\neq{\rm NP}\cap$ co-NP for infinite time Turing machines,” J.~Logic Comput., vol. 15, iss. 5, pp. 577-592, 2005.
@ARTICLE{DeolalikarHamkinsSchindler2005:NPcoNP,
AUTHOR = {Deolalikar, Vinay and Hamkins, Joel David and Schindler, Ralf},
TITLE = {{${\rm P}\neq{\rm NP}\cap$} co-{NP} for infinite time {T}uring machines},
JOURNAL = {J.~Logic Comput.},
FJOURNAL = {Journal of Logic and Computation},
VOLUME = {15},
YEAR = {2005},
NUMBER = {5},
PAGES = {577--592},
ISSN = {0955-792X},
MRCLASS = {68Q05 (03D05 68Q15)},
MRNUMBER = {2172411 (2006k:68026)},
MRREVIEWER = {Peter G.~Hinman},
DOI = {10.1093/logcom/exi022},
URL = {http://dx.doi.org/10.1093/logcom/exi022},
month = "October",
eprint = {math/0307388},
archivePrefix = {arXiv},
primaryClass = {math.LO},
file = F,
}

Extending results of Schindler [math.LO/0106087] and also my paper with Philip Welch, we establish in the context of infinite time Turing machines that $P$ is properly contained in $NP$ intersect $coNP$. Furthermore, $NP\cap coNP$ is exactly the class of hyperarithmetic sets. For the more general classes, we establish that $P^+ = (NP^+\cap coNP^+) = (NP \cap coNP)$, though $P^{++}$ is properly contained in $NP^{++}\cap coNP^{++}$. Within any contiguous block of infinite clockable ordinals, we show that $P_\alpha$ is not equal to $NP_\alpha\cap coNP_\alpha$, but if $\beta$ begins a gap in the clockable ordinals, then $P_\beta = NP_\beta\cap coNP_\beta$. Finally, we establish that $P^f$ is not equal to $NP^f \cap coNP^f$ for most functions $f$ from the reals to the ordinals, although we provide examples where $P^f = NP^f \cap coNP^f$ and $P^f$ is not equal to $NP^f$.