Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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. –  sxd Jul 10 '12 at 18:19
    
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})$ –  Jozef Jul 10 '12 at 18:44
    
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. –  Jeremy Hurwitz Jul 10 '12 at 20:47
    
I think he got the NP part. Completeness, OTOH, seems tricky... –  Michaël Cadilhac Jul 10 '12 at 20:48
    
BTW, I think it could be even $P$. –  Jozef Jul 10 '12 at 20:50

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
My God, this is brilliant. I stuck on this one for at least an hour before giving up. Thank you. –  Michaël Cadilhac Jul 11 '12 at 4:19
    
@Henning: What is basically the difference between $3sat$ to $3cnf$? –  Jozef Jul 11 '12 at 6:28
    
@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. –  Henning Makholm Jul 11 '12 at 11:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.