Talk:Turing reduction

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Low Importance
 Field: Foundations, logic, and set theory
This article has comments.
WikiProject Computer science (Rated B-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 

Weaker and stronger[edit]

What are called "weaker" reductions here (e.g. many one reduction) are called "stronger" reductions elsewhere in Wikipedia (eg, see http://en.wikipedia.org/wiki/Reduction_(recursion_theory)#Reductions_stronger_than_Turing_reducibility).

This confusion should be cleared up. The reductions are perhaps weaker in that, if you wanted to do a reduction of one problem to another, in a practical sense, and you had only the technique of many one instead of turing reducibility, you would be weaker at doing reductions than someone who was allowed to use turing reducibility. However, this is a derivative notion of "weakness". many one is actually stronger than turing reducibility because as a relation it has finer equivalence classes. 32F 05:19, 3 June 2007 (UTC)

32F corrected the problem; I added a short explanatory note and fixed the same problem on Truth table reduction. Leave a note if you find any other places, and I'll do a brief check right now. skeptical scientist (talk) 14:43, 10 June 2007 (UTC)
Thank ss, but I think your explanatory note harks back to the orginal confusion. The reductions provided by Many-One are stronger, not weaker, than the Turing reductions, because they give you a lot more information about the problem (after all each individual Many-One reduction is a Turing Reduction plus something extra that a Turing Reduction does not require) What I believe you mean to say is that, if what you want is to have some tools in your toolbox to perform reductions, for, say, some practical reason, then the Turing Reduction tool is stronger than the Many-One Reduction tool, since it allows you to perform more reductions, (even though those reductions themselves are individually weaker (but if all you need is a reduction, then this does not matter)). I am not sure how to phrase this elegantly so I refrain from trying for the time being... 32F 01:39, 18 June 2007 (UTC)


Yeah, that's what I was saying. I'm hopeful that I explain what I mean by "more/less powerful" as well as what is meant by "stronger/weaker" in a way that alleviates confusion, but if you have a way of making things more clear, be my guest. skeptical scientist (talk) 20:27, 19 June 2007 (UTC)

Copied[edit]

This article is obviously copied from http://encyclopedia.lockergnome.com/s/b/Turing_reduction (or possibly the other way around). What's wikipedia's policy on this?

The site you give is copied from here and links to this page (see the link labeled Source). Generally, if it looks an awful lot like a Wikipedia article, including links and our usual format, then it is probably copied from us. We freely allow all our content to be copied under the conditions of the GFDL; see Wikipedia: Copyrights. See also Wikipedia: Forks and mirrors for an incomplete list of many sites that copy us, many of which fail to credit us or follow the terms of the GFDL correctly.
If you do find a page from which we copied content, this should be dealt with promptly according to the policy at Wikipedia:Copyrights#If you find a copyright infringement. If you find your own copyrighted material in a Wikipedia article, visit Wikipedia:Request_for_immediate_removal_of_copyright_violation. I hope this helps. Deco 23:28, 5 May 2005 (UTC)
Thanks and sorry for wasting your time.
Don't worry, we appreciate you trying to help. Keep your eyes open; you may spot a real infringement in the future. Deco 08:39, 6 May 2005 (UTC)

Is the word "problem" ever formally defined in complexity theory? I presume when "problem" is mentioned this refers to some set which is computable (perhaps with the aid of an oracle), but it is disturbing to me to see it used in so many places without being formalized. - Gauge 04:45, 19 September 2005 (UTC)

I just observed that function problem is given as a type of "problem". Is this the general definition that I am looking for? - Gauge 04:47, 19 September 2005 (UTC)

What...[edit]

... are M and L in the introduction to this article?

update: I think I was able to fix that (hope my fix reflects the original authors intentions) --Björn Engelmann (talk) 10:02, 4 April 2013 (UTC)

Something wrong with the third paragraph[edit]

"Many important complexity classes such as NP are not closed under Turing reductions."

"However, a number of classes within P, such as L, NL, SL, and P itself, are closed under Turing reductions." (emphasis mine)

Supposing that both of these are correct, then P != NP. But that's not known at present. Ergo one (or both) of these claims must also be unproven.

Yes, as stated that paragraph implies P != NP. I've changed "are not closed" to "are not believed to be closed". --Saforrest 20:54, 8 November 2005 (UTC)


Back to this:

However, a number of classes within P, such as L, NL, SL, and P itself, are closed under Turing reductions.

Every computable set is Turing reducible to every other computable set (just ignore the oracle). So unless every set is in P, L, NL, and SL, the quoted sentence is wrong. CMummert 02:46, 27 July 2006 (UTC)

Edit on 2006-7-28[edit]

I moved this from the main page. It is covered better in the page Reduction (complexity), and doesn't fit here. None of the classes studied in computational complexity are closed under Turing reductions (except the class of all computable sets). They may be closed under weaker forms of Turing reduction; that is what the new section weaker reductions is for.

If CC = C for some class of problems C, we say that C is closed under Turing reductions. Demonstrating a Turing reduction from a problem A to a problem in such a class C shows that A ∈ C. Many important complexity classes such as NP are not believed to be closed under Turing reductions. In particular, any decision problem can be Turing-reduced to its complement, by simply solving the original problem and inverting the answer, showing that any class not closed under complement is also not closed under Turing reductions. However, a number of classes within P, such as L, NL, SL, and P itself, are closed under Turing reductions.

CMummert 12:54, 28 July 2006 (UTC)

Error[edit]

". . .a Turing reduction from a problem A to a problem B is, intuitively, a reduction which easily solves B, assuming A is easy to solve."

Isn't this backwards? If A is Turing reducible to B then A is decidable in B, which means that if B is easy to solve (ie. we have an oracle for B) then A is decidable. See Homer, S and Selman, A. Computability and Complexity Theory. pg 60, Springer, 2001.

Merge of relative computability[edit]

The relative computability article is little more than a stub. Merging those definitions into this article would be simple, and helpful because the topics are practically synonymous. The introduction to that article would be a good basis for a history section in this article. CMummert 22:51, 26 August 2006 (UTC)

cite.php[edit]

Any objections if I redo the references in cite.php ({{cite book}} etc.)? CMummert 02:11, 5 January 2007 (UTC)

Technical[edit]

I added the technical template, mainly because of the Example section, which I think probably is incomprehensible to most people likely to be using this page, and which could probably be rewritten to be more understandable. In particular, I see no reason to quote the s-m-n theorem, and no explanation is given of what an effective pairing function might be. Also, we probably don't actually need to prove A \equiv_T B, since the example works just as well if we just explain why A \leq_T B (or vice versa). I think a simpler example might be better, but I don't have a good one of the top of my head. Alternatively, I think this same example could be used but made more accessible. It might also be nice to give an example with 0 <_T A <_T B, perhaps with A=K and B={e : We is infinite}?

I'm not sure which, if any, of the other sections might be too technical to readers. The rest of the article doesn't seem too bad to me. skeptical scientist (talk) 15:19, 29 July 2008 (UTC)

Adding the template just for the example section is probably a bit much, but ok. Generally, there are much more problematic articles and since time is a scarce commodity, I think it's better to only tag the worse articles (that really don't make much sense). --C S (talk) 00:17, 31 July 2008 (UTC)