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!

  • 0
    Well, I think that you can split any 3CNF formula ( with more than one clause) into two 3CNF formula's with that property since they are connected with a conjunction. However, I am not sure about the construction to get: the original formula satisfiable if and only if the two split formulas are satisfiable2012-07-10

1 Answers 1

6

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.

  • 0
    @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.2012-07-11