• 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, p. 577–592, 2005.
  [Bibtex]

  @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$.