1
$\begingroup$

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.

  • 0
    Please note that we now have a http://cs.stackexchange.com :)2012-03-10
  • 0
    @J.D.: cs.stackexchange.com is currently in private beta.2012-03-10
  • 0
    @TsuyoshiIto Is this a problem?2012-04-05

2 Answers 2

0

(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.

1

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

  • 0
    If you mean literals, there are 2000 literals. There can be many different variables since variables can be reused in between clauses of CNF formulas.2012-03-10
  • 0
    Wait, so for 1), since the number of variables in the first 1000 clauses is upperbounded by 2000, we can find a way to satisfy 3/4 of them in P time. To satisfy the rest is the same as normal 2SAT? Then for 2), finding the satisfying assignment for the first 1000 is clearly in P time, but then finding 3/4 of the rest, I am not sure. Am I understanding what you are getting at or am I just completely off?2012-03-11
  • 0
    You got the gist of it.2012-03-11
  • 0
    So is finding a way to satisfy 3/4 of an unknown number of clauses in P time? Maybe it is in P time to just see how many clauses there are and then to satisfy them is just in P time as well since we can find out how many there are?2012-03-11
  • 0
    It is always possible to satisfy at least 3/4 of the clauses, if each one contains exactly two distinct literals. This may or may not be helpful in your case.2012-03-11
  • 0
    But since there is no way of figuring out if the literals are distinct, we can't really say that can we?2012-03-11