Talk:Reduction (complexity)

From Wikipedia, the free encyclopedia

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)

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)

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