This
level-5 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
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?
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)
... 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)
"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.
Back to this:
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)
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.
CMummert 12:54, 28 July 2006 (UTC)
". . .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.
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)
Any objections if I redo the references in cite.php ({{ cite book}} etc.)? CMummert 02:11, 5 January 2007 (UTC)
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 , since the example works just as well if we just explain why (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 , 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)
The comment(s) below were originally left at Talk:Turing reduction/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
Could this be made more accessible, for instance by briefly glossing some of the links which the article relies on? Geometry guy 12:53, 11 June 2007 (UTC) |
Last edited at 12:53, 11 June 2007 (UTC). Substituted at 20:18, 1 May 2016 (UTC)
Oracle-machine is so generic and flexible, algorithm is the real computation. It is not clair the name or the condition when reduction is valid: when an algorithm exist or when an oracle-machine exists? Please review article to be didactic about it. Krauss ( talk) 10:29, 13 September 2017 (UTC)
While I am not 100% confident that this is the case (or else I would have edited it myself), it seems like the first sentence from the section "The use of a reduction" contains an error:
Since every reduction from a set to a set has to determine whether a single element is in in only finitely many steps, it can only make finitely many queries of membership in the set .
Isn't this actually about reductions from to ?
The following is from the deleted Draft:Friedberg-Muchnik theorem. Would any of it be suitable for inclusion in this article? -- Beland ( talk) 19:05, 1 March 2022 (UTC)
The Friedberg-Muchnik theorem is a theorem about Turing Reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. [1] [2] It is a more general view of the Kleene-Post theorem. The Kleene-Post theorem states that there exist incomparable languages A and B below K. The Friedberg Muchnik theorem states that there exist incomparable, computabley enumerable languages A and B. Incomparable meaning that there does not exist a Turing Reduction from A to B or a Turing Reduction from B to A. It is notable for its use of the priority finite injury approach. [3]
References
This
level-5 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
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?
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)
... 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)
"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.
Back to this:
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)
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.
CMummert 12:54, 28 July 2006 (UTC)
". . .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.
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)
Any objections if I redo the references in cite.php ({{ cite book}} etc.)? CMummert 02:11, 5 January 2007 (UTC)
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 , since the example works just as well if we just explain why (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 , 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)
The comment(s) below were originally left at Talk:Turing reduction/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
Could this be made more accessible, for instance by briefly glossing some of the links which the article relies on? Geometry guy 12:53, 11 June 2007 (UTC) |
Last edited at 12:53, 11 June 2007 (UTC). Substituted at 20:18, 1 May 2016 (UTC)
Oracle-machine is so generic and flexible, algorithm is the real computation. It is not clair the name or the condition when reduction is valid: when an algorithm exist or when an oracle-machine exists? Please review article to be didactic about it. Krauss ( talk) 10:29, 13 September 2017 (UTC)
While I am not 100% confident that this is the case (or else I would have edited it myself), it seems like the first sentence from the section "The use of a reduction" contains an error:
Since every reduction from a set to a set has to determine whether a single element is in in only finitely many steps, it can only make finitely many queries of membership in the set .
Isn't this actually about reductions from to ?
The following is from the deleted Draft:Friedberg-Muchnik theorem. Would any of it be suitable for inclusion in this article? -- Beland ( talk) 19:05, 1 March 2022 (UTC)
The Friedberg-Muchnik theorem is a theorem about Turing Reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. [1] [2] It is a more general view of the Kleene-Post theorem. The Kleene-Post theorem states that there exist incomparable languages A and B below K. The Friedberg Muchnik theorem states that there exist incomparable, computabley enumerable languages A and B. Incomparable meaning that there does not exist a Turing Reduction from A to B or a Turing Reduction from B to A. It is notable for its use of the priority finite injury approach. [3]
References