What is Reduction?
Let L1 and L2 be two decision problems. Suppose algorithm A2 solves L2. That is, if y is an input for L2 then algorithm A2 will answer Yes or No depending upon whether y belongs to L2 or not.
The idea is to find a transformation from L1 to L2 so that algorithm A2 can be part of algorithm A1 to solve L1.
Learning reduction, in general, is very important. For example, if we have library functions to solve certain problems and if we can reduce a new problem to one of the solved problems, we save a lot of time. Consider the example of a problem where we have to find the minimum product path in a given directed graph where the product of the path is the multiplication of weights of edges along the path. If we have code for Dijkstra’s algorithm to find the shortest path, we can take the log of all weights and use Dijkstra’s algorithm to find the minimum product path rather than writing a fresh code for this new problem.
Introduction to NP-Complete Complexity Classes
NP-complete problems are a subset of the larger class of NP (nondeterministic polynomial time) problems. NP problems are a class of computational problems that can be solved in polynomial time by a non-deterministic machine and can be verified in polynomial time by a deterministic Machine. A problem L in NP is NP-complete if all other problems in NP can be reduced to L in polynomial time. If any NP-complete problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. NP-complete problems are the hardest problems in the NP set.
A decision problem L is NP-complete if it follow the below two properties:
- L is in NP (Any solution to NP-complete problems can be checked quickly, but no efficient solution is known).
- Every problem in NP is reducible to L in polynomial time (Reduction is defined below).
A problem is NP-Hard if it obeys Property 2 above and need not obey Property 1. Therefore, a problem is NP-complete if it is both NP and NP-hard.
NP-Complete Complexity Classes
Contact Us