Polynomial Time Reduction
Polynomial time reduction is a way of solving problem A by the hypothetical routine for solving different problem B, which runs in polynomial time.
Basically, the polynomial reduction is a way of showing that problem A is not harder than problem B.
- For example, we have some hypothetical algorithm, which can sort numerical data in some polynomial time. The input to the algorithm can only be in numeric form. Suppose we have a new problem to sort names of the cities across the country. What can be done?
- Suppose we don’t have an efficient algorithm to handle string data. We can apply some hashing functions on city names to map them to numeric values. Now, this is identical to the first approach. Thus, the polynomial reduction is the way of turning one problem into another problem whose solution can be found in polynomial time.
Reduction takes one of three forms :
- Restriction
- Local Replacement
- Component design
- Consider two decision problems A and B.
- Reduction from A to B transforms input x of A to equivalent input f(x) of B by applying some transformation function on x.
- So given an input x to A, the reduction algorithm produces an intermediate result f(x) to problem B such that f(x) to B returns “yes” only if input x to A returns “Yes”.
- Fig. 8.8.1 shows the scenario.
- Thus, we say A is polynomial time reducible to B if there exists some transformation function f(.) such that,
- Transformation function f(.) maps input x of problem A to f(x) such that, input f(x) to B produces the same answer as x would have produced for A.
- f(x) should be computable in the polynomial time of x. If such a function exists, we say A is polynomial time reducible to B, denoted as A ≤p B.
- A ≤p B implies if B ∈ P then A ∈ P. However, this does not imply if A ∈ P then B ∈ P.
- Polynomial time reductions are useful for studying the relative difficulty of different problems. For example, if A ≤p B and B is known to be NP-complete, then A is also NP-complete. Conversely, if A is known to be easier than B, then A ≤p B may be used to show that B is at least as difficult as A
- The figure shows the mode of reduction from one problem to other.
Youtube Channel: CodeCrucks