Prove NP-Completeness of a Problem (Complexity Theory)

Question

INPUT: A boolean formula F in CNF and a positive integer k.

OUTPUT: Decide if we can delete k clauses from F such that the resulting CNF is satisfiable.

Answer 1

Define

C(F, k) is true iff there exist k clauses whose deletion from F will result in a satisfiable formula.

Claim: C(F, k) is NP-complete.

Proof:

Need to proof that 1) It is NP-hard, and 2) It is in NP.

1)

To prove that it is NP hard show that regular satisfiability is reducible to C(F, k).

It is reducible because regular satisfiability is C(F, 0).

2)

To prove that C(F, k) is in NP consider the following non-deterministic algorithm.

Let n be the number of clauses, and m the number of variables in F.

Spawn (n chose k) processes one for each possibility of choosing k clauses.

And for each, spawn 2^m processes, one for each possible truth assignment to the variables.

Each process checks (in polynomial time) whether its truth assignment satisfies each

of the cluases of F, with the exeption of the k chosen ones.

If any process returns true then C(F, k) is true; it is false if no process returns true.

QED