> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/28.-reductions-and-decomposition/28.4-reductions-and-decomposition.md).
# 28.4 Reductions and Decomposition
Recall in previous section that to solve one problem (longest paths), we created a new graph G' and fed it into a different algorithm and then interpreted the result.
This process is known as **reduction**. Since DAG-SPT can be used to solve DAG-LPT, we say that "DAG-LPT reduces to DAG-SPT."
In other words, the problem of DAG-LPT can be reduced to the problem of DAG-SPT.
A problem like DAG-LPT can potentially be reduced to multiple other problems. As a real-world analogy, consider climbing a hill. There are many ways we can solve the problem of "climbing a hill."
* "Climbing a hill" reduces to "riding a ski lift"
* "Climbing a hill" reduces to "being shot out of a cannon"
* "Climbing a hill" reduces to "riding a bike up the hill"
Formally, **if any subroutine for task Q can be used to solve P, we say P reduces to Q.**
This definition is visualized below:
Note that this is simply a generalization of the first graphic on this page. P reduces to Q since Q is used to solve P. This works by preprocessing the input �x into �y, running the algorithm Q on �y, and postprocessing the output into a solution for P. This is what we did for reducing DAG-LPT to DAG-SPT.
#### Example
Here we'll show how one problem can reduce to a seemingly unrelated different problem. First, the two problems:
**Independent Set Problem**
An independent set is a set of vertices in which no two vertices are adjacent.
The Independent Set Problem: Does there exist an independent set of size k? In other words, can we color k vertices red, such that none touch?
Example of independent sets solutions for k=2 and k=4
**3SAT Problem**
What values of `x1`, `x2`, `x3`, `x4` satisfy the following boolean formula: `(x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)`?
The 3SAT Problem: Given a boolean formula, does there exist a truth value for boolean variables that obeys a set of 3-variable disjunctive constraints?
Terminology clarification:
* Constraints are True/False values.
* **Disjunctive** means separated by OR. 3SAT has a set of "clauses," each made up of 3 literals with each literal separated by an OR. For example, the first clause above is `(x1 || x2 || !x3)`.
* In the 3SAT problem we must satisfy the entire set of clauses (combine each clause with AND).
**e.g.:** `(x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)` Yes, a solution for x1, x2, x3, x4 exists Solution: x1 = true, x2 = true, x3 = true, x4 = false
**Reduction**
**CLAIM**: 3SAT reduces to Independent Set
* Recall this means we claim we can solve 3SAT by using the Independent Set algorithm!
**PROOF**: To prove the reduction, we need to argue that we can:
1. Preprocess a given 3SAT problem
2. Solve it with Independent Set
3. Postprocess the output of part 2 into a solution to the original 3SAT problem.
Let's do it!
***Preprocess a given 3SAT problem*** Given an instance X of 3SAT, preprocess it into a graph G:
1. For each clause in X, create 3 vertices in a triangle
2. Add an edge between each literal and its negation
***Solve with Independent Sets*** On graph G, find an independent set of *size = number of clauses in 3SAT*.
***Postprocess the output*** Elements in the independent set are considered "True", while elements outside are considered "False." If you can find an independent set of size = number of clauses in 3SAT, then you've successfully solved 3SAT (using independent sets whoo!).
In the above example, since `x3`, `!x2`, `x3`, `x4` were picked for the independent set, we consider each of those literals to be True and values for the rest don't matter. Therefore, `x3 = True, x2 = False, x4 = True, x1 = doesn't matter.`
**Why this works:** We'll reference the below example when going through the proof.
`(x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)`
The above 3SAT problem has 3 clauses. To form a satisfying truth assignment we must pick one literal from each clause and give it the value True. Of course, we must be consistent. If we choose `x1` to be True in the first clause, we can't choose `!x1` to be True in the third clause (x1 can't both be True and False!).
Representing a clause by a triangle forces us to pick only literal in a clause for the independent set. Repeat this for every clause and and finding an independent set of *size = number of clauses* means exactly one literal will be picked from each clause (we'll consider a picked node to be True).
We also make sure to add an edge from each literal to its negation to prevent us from choosing opposite literals (e.g. both `x1` and `!x1`) in different clauses. This may also have the effect of finding an independent set impossible - in this case, 3SAT is also not solvable.
Here's a visualization of the above reduction:
Note that reductions are a general concept and apply to many different types of problems (they don't always involve creating graphs!)
### Reflection
One can argue that we have been doing reduction all throughout the course.
* Abstract Lists reduce to arrays or linked lists
* Percolation reduces to Disjoint Sets
* Maze generation reduces to \[your solution here ;)]
However these aren't exactly reductions because you aren't using a single other algorithm to solve your problem. Notably, in the earlier reduction example we used the Independent Sets algorithm as a '[black box](https://en.wikipedia.org/wiki/Black_box)' to solve 3SAT.
Perhaps a better term for what we've been accomplishing earlier in the course is *decomposition* - breaking a complex task into smaller parts. Using abstraction to make problem solving easier. This is the heart of computer science.