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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
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.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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:
- a is a YES-instance for A if and only if b is a YES-instance for B.
(A YES-instance is an instance of the decision problem whose answer is YES/True).
- The transformation takes polynomial time in the size of a.
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".
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.