Proofs

Practice Problem: Sparse Subgraph

Yet another NP-Completeness practice problem. This time from Graph Theory.

Practice Problem: Almost-SAT

If you are reviewing Theory of Computation, here is a nice and simple example of NP-Completeness proof.