P is not equal to NP intersect coNP for Infinite Time Turing Machines

Details P is not equal to NP intersect coNP for Infinite Time Turing Machines P is not equal to NP intersect coNP for Infinite Time Turing Machines

2003-07-30

arxiv.org/abs/math/0307388v1

Mathematics

Logic

26 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

P is not equal to NP intersect coNP for Infinite Time Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with P is not equal to NP intersect coNP for Infinite Time Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and P is not equal to NP intersect coNP for Infinite Time Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-334103