I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences.

Please can anyone explain it in detailed version ?

  • 3
    $\begingroup$ Possible duplicate of What does a polynomial time reduction mean? $\endgroup$
    – Badr B
    Jun 2 '18 at 18:44
  • 1
    $\begingroup$ There are many descriptions already. What didn't you understand about them? I'm not trying to be sarcastic -- it's just that, without some guidance about what you actually need, it seems quite likely that somebody will explain it to you and you'll say, "Sorry, I don't understand that, either." $\endgroup$ Jun 2 '18 at 20:02

I think your best bet is probably to get an introductory text on the theory of computation and/or take a course on the subject. I think the typical courses teach quite a lot before getting to polynomial time reduction, so you are most likely skipping over a lot prerequisite material. I'll try to give a common language understanding of what a polynomial time reduction is without too many details.

First you have to understand what a reduction is, so I would start here. To quote the linked wikipedia page:

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

If you want to understand it precisely you should carefully read the definition section of the page. The situation where we are interested in reductions can be roughly described as attempting to encode problems that we know are "hard" or complete for a class as a newly defined problem that we are unsure about. This will prove that the new problem is at least as hard as the one that we know to be hard.

In the vaguest sense you can think of a polynomial time reduction as a reduction that requires $O(n^k)$ steps (for a fixed k). So we require polynomial time in order to transform any instance of the "hard" problem into an instance of the new problem. Again the wiki page gives a description of different types of polynomial time reductions.

  • $\begingroup$ Thank you so much. The reduction definition helped me understand the polynomial-time reduction. $\endgroup$
    – Goktug
    Jun 2 '18 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.