${\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.  
    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$.

Leave a Reply