Talk:Reduction (complexity)

Untitled

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)

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)

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)

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)

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

Detailed example

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)

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)

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)

problem: "reducing squaring to multiplication"

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)

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)

contradiction - usage of the term `hard'

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)

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)

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)

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

Image doesn't look like a vertex cover

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)

Sloppy lede

"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)