Polynomial-Time Reduction

Question

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 ?

Answer 1

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.