Watched Eric Demaine's lecture and initially did not understand the reduction from 3-SAT to 3-dimensional matching.
- Complexity: P, NP, NP-completeness, Reductions https://youtu.be/eHZifpgyH_4?t=2786
To reduce 3-SAT to 3DM, we need to show how to express every 3-SAT problem as a 3DM problem. If 3DM has a solution, then that solution can be applied to solve any 3-SAT problem.