2
$\begingroup$

I am working with the following definition of the conjunctive normal form of a propositional formula:

A formula $\phi$ with propositional variables $P_1 \ldots P_n$ is said to be in conjunctive normal form if $\phi = (C_1 \land \cdots \land C_m)$ where for each $1 \leq k \leq m$, $C_k$ is a distinct formula of the form $L_{1k} \lor \cdots \lor L_{nk}$ with $L_{ik} \in \{P_i, \neg P_i \}.$ In addition, we say that the formula $P \lor \neg P$ is in conjunctive normal form. We refer to the $C_k$'s as the CNF constituents of $\phi$.

It is known that to find the CNF of a formula, we look at the truth table for that formula and write down a constitutent for each assignment to variables in which the formula is false, saying the formula is false in that case. That is, if a formula is false in the case where $P$ is true and $Q$ is false, we include the constituent equivalent to $\neg (P \land \neg Q)$, i.e., we include $(\neg P \lor Q)$.

Given a formula already in CNF, it seems easy to determine whether the formula is satisfiable: we merely need to determine how many constituents the formula contains. If the formula is unsatisfiable, it is false in every case and so contains every possible constitutent. If the formula has $n$ variables there are $2^n$ possible assignments to variables; if the CNF formula has less than $2^n$ constituents, then, it must be satisfiable. The number of constituents is determined by the number of times the symbol $\land$ appears in the formula. To do this does not require anything other than reading the formula from left to right. I do not see how this is anything other than polynomial in the length of the input, which I am taking to be the length of the formula.

Obviously, however, SAT is an NP-complete problem and showing it is P would probably be a lot harder than the simple observation above. Any help identifying what I am missing would be appreciated.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

This is one way to obtain the conjuctive normal form, but not every conjuctive normal form can be assumed to be constructed in this way.

For example, $A \land \neg A \land B$ is not satisfiable, despite only containining 3 constituents.

Of course, you are right that your construction would give $(\neg A \lor \neg B) \land (\neg A \lor B) \land (A \lor \neg B) \land (A \lor B)$, which has 4 constituents.

$\endgroup$
5
  • $\begingroup$ This is true, for your formula, but only because you seem to be using a different definition of CNF than I am. According to the definition of CNF above, every constituent must mention every propositional variable. I do not see how your formula is in CNF? $\endgroup$
    – rea_burn42
    Commented Jan 18 at 22:59
  • 3
    $\begingroup$ The definition of CNF used by @rea_burn42 is sometimes called "fully developed" or "fully expanded" CNF. It is, in general, exponentially longer than the ordinary CNF in this answer. So polynomial time relative to the fully expanded CNF amounts to exponential time relative to the ordinary CNF. $\endgroup$ Commented Jan 18 at 23:08
  • 1
    $\begingroup$ @rea_burn42 You're right, I didn't notice that your definition is a bit different to what I'm used to. I think you're completely correct in your reasoning. This isn't in violation of SAT being NP-complete, since your definition is exponentially longer. (Edit - Andreas beat me to it - thank you!) $\endgroup$
    – FlipTack
    Commented Jan 18 at 23:09
  • 1
    $\begingroup$ This discussion seems to solve it, thanks so much! So SAT for fully expanded CNF must be polynomial time. $\endgroup$
    – rea_burn42
    Commented Jan 18 at 23:10
  • $\begingroup$ @FlipTack nice work on this answer, you beat me to it! $\endgroup$
    – emesupap
    Commented Jan 18 at 23:12

You must log in to answer this question.

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