np-completeness

• 15 Dec 2018

  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...
• 14 Dec 2018

  Practice Problem: Almost-SAT

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