- V. Deolalikar, J. D. Hamkins, and R. Schindler, “P $\neq$ NP $\cap$ co-NP for infinite time Turing machines,” Journal of Logic and Computation, vol. 15, iss. 5, pp. 577-592, 2005.
@ARTICLE{DeolalikarHamkinsSchindler2005:NPcoNP, AUTHOR = {Deolalikar, Vinay and Hamkins, Joel David and Schindler, Ralf}, TITLE = {P $\neq$ NP $\cap$ co-NP for infinite time {T}uring machines}, JOURNAL = {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://jdh.hamkins.org/np-conp/}, 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$.