P is not equal to NP intersect coNP for Infinite Time Turing Machines
| dc.creator | Deolalikar, Vinay | |
| dc.creator | Hamkins, Joel David | |
| dc.creator | Schindler, Ralf-Dieter | |
| dc.date | 2003-07-30 | |
| dc.date.accessioned | 2026-07-07T04:59:58Z | |
| dc.date.available | 2026-07-07T04:59:58Z | |
| dc.description | Extending results of Schindler [math.LO/0106087] and Hamkins and Welch [math.LO/0212046], we establish in the context of infinite time Turing machines that P is properly contained in NP intersect coNP. Furthermore, NP intersect coNP is exactly the class of hyperarithmetic sets. For the more general classes, we establish that P+ = (NP+ intersect coNP+) = (NP intersect coNP), though P++ is properly contained in NP++ intersect coNP++. Within any contiguous block of infinite clockable ordinals, we show that P_alpha is not equal to NP_alpha intersect coNP_alpha, but if beta begins a gap in the clockable ordinals, then P_beta = NP_beta intersect coNP_beta. Finally, we establish that P^f is not equal to NP^f intersect coNP^f for most functions f from the reals to the ordinals, although we provide examples where P^f = NP^f intersect coNP^f and P^f is not equal to NP^f. | |
| dc.description | 26 pages | |
| dc.identifier | https://arxiv.org/abs/math/0307388 | |
| dc.identifier | http://arxiv.org/abs/math/0307388 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68206 | |
| dc.subject | Logic | |
| dc.subject | 03D15; 68Q15; 68Q17; 03E15 | |
| dc.title | P is not equal to NP intersect coNP for Infinite Time Turing Machines | |
| dc.type | text |