On the questions P?= NP ∩ co-NP and NP?= co-NP for infinite time Turing machines

الأصل · EN

Schindler recently addressed two versions of the question P?= NP for Turing machines running in transfinite ordinal time. These versions differ in their definition of input length. The corresponding complexity classes are labelled P, NP and P+, NP+. Schindler showed that P ≠ NP and P+ ≠ NP+. We show that P = NP ∩ co-NP and NP ≠ co-NP, whereas P+ ⊂ NP ∩ co-NP and NP+ ≠ co-NP+.