On the Power of Positive Turing Reductions

Details On the Power of Positive Turing Reductions On the Power of Positive Turing Reductions

1999-06-26

arxiv.org/abs/cs/9906028v1

Computer Science

Computational Complexity

7 pages

Scientific paper

In the early 1980s, Selman's seminal work on positive Turing reductions showed that positive Turing reduction to NP yields no greater computational power than NP itself. Thus, positive Turing and Turing reducibility to NP differ sharply unless the polynomial hierarchy collapses. We show that the situation is quite different for DP, the next level of the boolean hierarchy. In particular, positive Turing reduction to DP already yields all (and only) sets Turing reducibility to NP. Thus, positive Turing and Turing reducibility to DP yield the same class. Additionally, we show that an even weaker class, P(NP[1]), can be substituted for DP in this context.

Affiliated with

Also associated with

No associations

Rating

On the Power of Positive Turing Reductions 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 Power of Positive Turing Reductions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Power of Positive Turing Reductions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499796