7
$\begingroup$

I'd like your help with understanding whether the following problem is in $P$, $NP$, $NPC$.

The problem $B$:

Input: a $3CNF$ formula which contains more than one clause.

output: Can we divide the formula to two $3CNF$ satisfiable clauses?

I'd really like to learn how to analyze this kind of questions.

First I know that in order that the problem would be in $NP$ I need to find a polynomial verifier to the problem, so I can check all the options for partitions and see if it's satisfies the problem. so the problem is probably in $NP$, in order to know whether it is complete, I need to find a reduction from a NP-hard problem, first one came to my head is $3SAT$, but how a suitable reduction would look like? or maybe it is simply in $P$? what is the way for deciding this?

I'd really appreciate some explanations.

Thanks a lot!

$\endgroup$
6
  • 1
    $\begingroup$ Do you actually mean that you can divide the formula in to two 3CNF formulas which are satisfiable? Or that two clauses in that formula are satisfiable, these two things are not the same. $\endgroup$
    – sxd
    Jul 10, 2012 at 18:19
  • $\begingroup$ The first thing you said. For $(a V \bar{b} V c) \wedge (\bar{a} V b V c) \wedge (a V b V \bar{c})$ to $(a V \bar{b} V c)$ and $(\bar{a} b V c) \wedge (a V b V \bar{c})$ $\endgroup$
    – Jozef
    Jul 10, 2012 at 18:44
  • $\begingroup$ To show that a problem is in NP, you need to give the certificate and the verifier. In this case, the certificate consists of both the split and the two satisfying assignments. The verifier checks that the split is valid and that the provided assignments satisfy them. $\endgroup$ Jul 10, 2012 at 20:47
  • $\begingroup$ I think he got the NP part. Completeness, OTOH, seems tricky... $\endgroup$ Jul 10, 2012 at 20:48
  • $\begingroup$ BTW, I think it could be even $P$. $\endgroup$
    – Jozef
    Jul 10, 2012 at 20:50

1 Answer 1

6
$\begingroup$

The following program solves problem $B$ in constant time:

Input B.
Output "yes".

To see that "yes" is always the right answer, consider that we can divide the input into one set of clause where each clause contains at least one positive literal, and another set where each clause contains at least one negative literal. The first set can be satisfied by making everything true; the second can be satisfied by making everything false.

(In the special case where one of the sets just described is empty, the original 3CNF formula must be satisfiable, and so any partition of it will work).


The above solution assumes that you're allowed to mix and match between the clauses in the input. If you must preserve the order of the clauses and just divide the initial 3CNF into a "front end" and a "back end", then the problem is NP-complete, by reduction from 3SAT itself: Given any 3CNF formula, choose a fresh variable $x$ and append the two clauses $x\lor x\lor x$ and $\bar x\lor \bar x\lor \bar x$. The only way to split the extended formula into satisfiable parts is to split between the new clauses, which means that the extended formula is in $B$ exactly if the original one was satisfiable.

$\endgroup$
3
  • $\begingroup$ My God, this is brilliant. I stuck on this one for at least an hour before giving up. Thank you. $\endgroup$ Jul 11, 2012 at 4:19
  • $\begingroup$ @Henning: What is basically the difference between $3sat$ to $3cnf$? $\endgroup$
    – Jozef
    Jul 11, 2012 at 6:28
  • $\begingroup$ @Jozef: A persistent typo/braino in my answer, sorry. 3SAT is the problem; 3CNF is the class of formulas that are input to the problem. $\endgroup$ Jul 11, 2012 at 11:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .