Talk:Reduction (complexity)

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale. Computer science Low‑importance 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Low This article has been rated as Low-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Seems like we should merge in Reduction (recursion theory), since the method is basically the same between recursion theory and complexity theory. Thoughts? Bihzad (talk) 03:11, 5 April 2012 (UTC)Reply

There is also a lot of overlap between this page and the pages on specific reductions: Turing reduction and many-one reduction. In an ideal world, someone would organize things better. — Preceding unsigned comment added by 69.172.172.171 (talk) 20:23, 9 January 2014 (UTC)Reply

There is an error in the diagram in the top right-hand corner. In the first group of three nodes the B should be coloured rather than the A. —Preceding unsigned comment added by 129.78.64.102 (talk) 06:21, 9 June 2009 (UTC)Reply

For the definition of closed can A be a member of S since A is a member and not a subset of N? --Twchui 16:15, 12 July 2005 (UTC)Reply

The definition of closed has been updated. Pro8 22:03, 17 December 2005 (UTC)Reply

The "Detailed example" seems problematic. It seems S only decides whether or not M will accept or reject a given input w. This seems to imply that S will always determine M to halt, either by accepting or rejecting w. The halting problem for M asks whether M halts or not on the input w, not just whether it accepts or rejects w. How does S indicate when M does not halt on w? How is this distinguished from when M halts but rejects w? - 69.174.134.88 07:43, 12 June 2006 (UTC)Reply

Attempted a fix. N is defined by the following behavior:

if( input is w AND

(M(w) accepts OR M(w) rejects) ) then

accept

else

do not halt (infinite loop, for instance)

Then obviously N does not solve the halting problem since it never rejects w if M does not halt on input w. - 69.174.134.88 22:41, 12 June 2006 (UTC)Reply

I just spent ages trying to work out what the sentence "S creates a Turing machine N that accepts only if the input string to N is w and M halts on input w, and does not halt otherwise." means. I think I would define N by the following behaviour which I think works and is clearer:

if (input ≠ w) then

reject

else

simulate M on input w indefinitely until M halts (in either the accepting or rejecting state).

accept

I also wasted ages trying to work out what was wrong with the original text and why the fix was needed, so I thought I'd try to write an explanation here. The original text "S creates a Turing machine N that rejects all strings except w, but on input w works just like M." from the revision at 11:42, 24 May 2006 was wrong. If the input is w and M(w) rejects, then N will reject as well because it "works just like M". But clearly M has halted so N should have accepted.

"S creates a Turing machine N that accepts only if the input string to N is w and M halts on input w, and rejects otherwise." from the revision at 07:22, 12 June 2006 was wrong because of the "rejects otherwise" bit. It looks like N actually solves the halting problem because it somehow knows to reject when M doesn't halt. We can't assume we can solve the halting problem because that's the very thing we're trying to prove (all under the assumption that R exists). "S creates a Turing machine N that accepts only if the input string to N is w and M halts on input w, and does not halt otherwise." from the revision at 21:59, 12 June 2006 fixes this, but I don't think its meaning is very clear.

Egriffin 07:57, 1 July 2007 (UTC)Reply

first of all, shouldn't this be the other way around? by the definition at the top, what's being described is a reduction from multiplication to squaring, i.e. reducing any multiplication problem to a squaring problem (also given addition and subtraction), not the other way around. also, the reduction described requires that you be able to divide by 2, which isn't mentioned as one of the requirements, and is non-trivial (at best) to express using only addition and subtraction.

Benwing 21:41, 7 September 2006 (UTC)Reply

Yes, the reduction is from multiplication to squaring. I'm not sure what the best way is to address the division by 2 thing - in many cases it doesn't matter, as having double the product is good enough - but for argument's sake I just added "division by 2" to the list of permitted operations. Deco 00:07, 8 September 2006 (UTC)Reply

What? Was this written by a third grader? Something being "hard" to solve is a wholly subjective phenomenon. Aside from that, the application of a new technology or idea to an old phenomenon or problem which simplifies it, does not imply that utilization of the new idea on a formerly complex problem creates a paradox, or that the new, simpler idea or technology is "hard." It simply means that the previous methodology rendering the previous action "hard" has been rendered invalid, as a sufficient new methodology has been created as to simplify the previous problem, and it becomes, an "easy" problem to solve via reduction.

wow. youre right. brilliant!!! ----88.64.153.44 17:23, 30 March 2007 (UTC)Reply

The use of the word "hard" is pretty standard in the field and is used in a formal sense to describe problems such that every problem in a class reduces to them. Maybe you're not clear on the concept that "B is hard and there exists a reduction from A to B implies A is hard". Reductions are used both to show easiness and hardness of problems - there is no contradiction. If you think the discussion is too informal or verbose it could be made more formal. Dcoetzee 10:52, 2 April 2007 (UTC)Reply

I agree, the use of ``hard" is appropriate here. If you do not agree then add a definition to explain what hard means in this context. Bah23 15:51, 27 April 2007 (UTC)Reply

Dcoetzee, shouldn't your statement read "...a reduction from B to A..."? --Doradus (talk) 01:24, 10 October 2009 (UTC)Reply

Sorry if this is a dumb question, but the introductory diagram on the current version of the page contains an edge between two white vertices both labeled "B". This edge is not incident to a blue vertex, so I don't understand how the blue vertices form a vertex cover. --Doradus (talk) 01:20, 10 October 2009 (UTC)Reply

"reduction is an algorithm for transforming one problem into another problem." - this is a many-one reduction. The Turing reduction is using the solution of one problem to solve another one. The latter can hardly be formally described as "transforming the problem". 22:29, 2 December 2015 (UTC)