P or NP-Complete? (concerning 2-CNF formulas)

Question

I have two languages that I want to either prove is in P or NP-complete.

1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest.

2) 2-CNF formulas where there exists an assignment that satisfies the all of the first 1000 clauses and 3/4 of the rest.

Intuitively, I want to say that 1) is P and 2) is NP-complete, but I am not sure and don't know how to prove my intuition. I am assuming that 2SAT is what I will need to reduce from for 1). If 2) is in P, then 2SAT should also be a good candidate, but I don't know if it's in P.

Answer 1

(1) is clearly in P -- actually it is solvable in linear time, since there are only $\binom{1000}{750}=O(1)$ different ordinary 2SAT problems to try, and each of these can be checked in linear time.

(2) is NP-complete, by reduction from the known NP-hard MAX-2-SAT problem which asks to recognize those $(A,k)$ such that $A$ is a set of 2-clauses with a $k$-element satisfiable subset.

Given $(A,k)$, pick a fresh variable $x_0$ and construct an input to your problem (2) consisting of

• 1000 copies of the clause $x_0\lor x_0$ -- these will be the 1000 clauses that must always be satisfied.
• the clauses in $A$.
• $3|A|-k$ copies of $x_0 \lor \neg x_0$ (these are automatically satisfied).
• $k$ copies of $\neg x_0 \lor \neg x_0$ (these can never be satisfied).

This gives an instance of (2) that must answer true exactly if $k$ clauses in $A$ can be satisfied simultaneously.

If you don't like clauses such as $x_0\lor x_0$ where the two literals are identical, they can be avoided without much trouble. On the other hand, the reduction breaks down if you restrict problem (2) to be about formulas that don't repeat any clause. I don't know if MAX-2-SAT is still NP-hard under restrictions that allow the reduction to be salvaged then.

Answer 2

Hint: How many variables are involved in the first 1000 clauses?