NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT≥k,,r-UNLSAT≥k)

摘要

k-CNF is the class of CNF formulas in which the length of each clause of every formula is k. The decision problem asks for an assignment of truth values to the variables that satisfies all the clauses of a given CNF formula. k-SAT problem is k-CNF decision problem. Cook [9] has shown that k-SAT is NP-complete for k ≥ 3. LCNF is the class of linear formulas and LSAT is its decision problem. In [3] we present a general method to construct linear minimal unsatisfiable (MU) formulas. NP = PCP(log, 1) is called PCP theorem, and it is equivalent to that there exists some r > 1 such that (3SAT, r-UN3SAT)(or denoted by (1 - 1/r) - GAP3SAT) is NP-complete [1][2]. In this paper,we show that for k ≥ 3, (kSAT, r-UNkSAT) is NP-completre and (LSAT, r-UNLSAT) is NP-completre for some r > 1. Based on the application of linear MU formulas[3], we construct a reduction from (4SAT, r-UN4SAT) to (LSAT_(≥4),r'-UNLSAT_(≥4)), and proved that (LSAT_(≥4),r - UNLSAT_(≥4)) is NP-complete for some r > 1, so the approximation problem s-Approx-LSAT_(≥4) is NP-hard for some s > 1.