On the Complexity of Subproblems of SAT (New Developments of Theory of Computation and Algorithms)
Akihiro Matsuura, Kazuo Iwama · Kyoto University Research Information Repository (Kyoto University) · 2001
In this paPer, we show some complexity results of subproblems of Satisfifiability Problem (SAT).We introduce adecision problem that asks if, given a $k$ -CNF formula with $n$ variables, there is a satisfying assingment with at most $pn$ variables set to 1.For $k$ $\geq 2$ , we show that (1) when $p=n^{c}$ $(-1