A reduction is a way of transforming one problem into another problem. Suppose you have a problem A which you do not know how to solve. However, you know about an algorithm to solve problem B. If you can "transform" problem A into an instance of problem B (call it instance A_B), you can use the known algorithm for B to solve the "transformed" version A_B, and obtain the solution for A with the solution attained, by "reversing the transformation". We then say that A reduces to B.
Through reductions, we have another tool to solve problems. Furthermore, with an efficient "transformation", reductions provide the ability to compare the "hardness" of different problems.
Given two decision problems A and B, a polynomial-time reduction from A to B, denoted A ≤p B, is a transformation from instance a of A to instance b of B such that:
With a polynomial-time reduction, we will be able to claim that the problem of solving A is only as hard as solving B.
However, if B is "hard", it does not imply that A is "hard". Likewise, if A is "easy", it does not mean that B is "easy".
This visualization shows the network of reductions from different NP-complete decision problems to another. In theory, since all these problems are NP-complete, they can all be reduced to one another, but the transformation can become very convoluted for some problems.
A vertex contains the name of an NP-complete decision problem. Hover over it to see its full name, or click on it to open the relevant slide that describes the problem.
An edge between vertices opens the slide which contains the proof of reduction from one problem to the other, in the direction of the arrow. [Soon: Green arrow indicates that we have digitize the reduction proof. Black arrow indicates that we have not done so.]
The Circuit-Satisfiability problem (C-SAT) is the decision problem of determining whether a given Boolean circuit (using AND, OR, NOT gates) has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called satisfiable. Otherwise, the circuit is called unsatisfiable.
A clique is a set of vertices such that there exists an edge between every pair of distinct vertices in the set. More formally, for a set of vertices C, ∀ v ∈ C, ∃ an edge (u, v) ∀ u ≠ v ∈ C. Then the size of the clique is the number of vertices in the set C.
The CLIQUE decision problem asks the following question on a graph G = (V, E): Does there exist a complete subgraph in G of at least size k?
Given a graph G = (V, E), a dominating set D is a subset of vertices such that for all other vertices u that are not in D, there exists some vertex v in D such that (u, v) is an edge in G (i.e., u is adjacent to v).
The Dominating-Set decision problem asks if given an integer k, there exists a dominating set in G of at most size k.