Talk:Polynomial-time reduction

From Wikipedia, the free encyclopedia

Needs more wikifying. Mathiastck 16:42, 1 March 2007 (UTC)

[edit] Reductions in P

So it's claimed that you can't polynomial-time reduce the problem which accepts everything (or rejects everything) to any other problem. Why not simply solve the problem in polynomial time (in particular, constant time) and make no calls to the problem you want to reduce to? Am I missing something.

If you're problem is that the output of the ancillary problem is ignored, I'd say this. As I see it, P is a class of problems, all of which can be polynomial-time reduced to each other, and it happens that we know how to solve some of them in polynomial time. That kind of characterization reflecting the definition of NP-c seems natural, and I think the definition should reflect that.

24.12.102.35 14:20, 23 March 2007 (UTC)

It's annoying, but the footnote is correct. The problem is that when performing a many-one reduction, you don't have a choice: you must invoke the problem you're reducing to, exactly once, at the end, and must return that answer. Consequently, nothing can be reduced to the trivial languages accepting/rejecting everything except themselves. Dcoetzee 00:29, 26 March 2007 (UTC)