Talk:Polynomial-time reduction

Untitled

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

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)

To me this semes wrong: "but still weak enough that polynomial-time reductions from problems in NP or co-NP to problems in P are considered unlikely to exist." Since P is inside NP such reductions must exist shold it not be NPC and co-NPC? 82.209.156.242 (talk) 12:29, 16 February 2009 (UTC)

 I think that the intent is that a reduction from an arbitrary problem in NP to a problem in P is considered unlikely to exist.  However, the statement is incredibly uninteresting.  — Preceding unsigned comment added by 136.159.108.136 (talk) 21:00, 27 March 2013 (UTC) 

Confusing

I've added a lead para to try to state the subject in a form free of technical jargon. Some mathematician will not doubt take action if I've got it wrong Chrismorey (talk) 23:15, 7 September 2013 (UTC)

Definitely an improvement in being less technical, but I think too vague to capture the idea of it being a polynomial time reduction. Additionally, your description in terms of transformations really only applies to many-one reductions and not to the other kinds of polynomial time reductions. And I don't understand what your sentence "This eliminates approaches to solving (or simplifying) the problem that are theoretically possible, but impractical." is supposed to mean. Anyway, your edit conflicted with a complete rewrite of the article that I was performing at the same time (mostly offline until I actually made the change about an hour after yours), including a different new lead; let me know what you think. —David Eppstein (talk) 00:29, 8 September 2013 (UTC)

See Also

I added a two bullet section on related topics. Feel free to add more. — Preceding unsigned comment added by 2607:F470:8:4058:FAB1:56FF:FEC5:B939 (talk) 23:45, 1 November 2014 (UTC)

I removed one of your two bullets, Turing reduction — it is already prominently linked in the main article text, so WP:SEEALSO says we shouldn't also include it here. —David Eppstein (talk) 00:11, 2 November 2014 (UTC)