On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines

Details On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines

2003-05-30

arxiv.org/abs/math/0305445v1

Mathematics

Logic

9 pages

Scientific paper

Schindler recently addressed two versions of the question P $\stackrel{?}{=}$ 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 ${\rm P}^+,{\rm NP}^+$. Schindler showed that P $\neq$ NP and ${\rm P}^+ \neq {\rm NP}^+$. We show that P $=$ NP $\cap$ co-NP and NP $\neq$ co-NP, whereas ${\rm P}^+ \subset$ NP $\cap$ co-NP and ${\rm NP}^+ \neq $ co-NP$^+$.

Affiliated with

Also associated with

No associations

Rating

On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP 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 On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the questions P ?= NP $\cap$ co-NP and NP ?= co-NP for infinite time Turing machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-395638