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

  • [DOI] 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.
    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$.

Leave a Reply