## proofs

### Practice Problem: Sparse Subgraph

0. Context This is a second practice problem on NP-Completeness proofs. The first one was Almost-SAT problem. 1. Problem...### Practice Problem: Almost-SAT

1. Problem Statement Consider the Almost-SAT problem defined as following: Input: A CNF formula $f$ with $n$ variables $...