Talk:Reduction (complexity)
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics rating: | Start Class | Low Priority | Field: Foundations, logic, and set theory | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
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)
[edit] 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)
- if( input is w AND
- 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
- if (input ≠ w) then
- 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:
-
- 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)
[edit] 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)
[edit] 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)
