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.

How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee c)\wedge(a\vee d)\wedge (b\vee d)\wedge (b\vee c)$, in which the size of the formula seems to expand exponentially. Therefore, I feel the problem should be in NPC. However, I do not have a clue of how to reduce this problem.

share|improve this question
add comment

2 Answers

It is true that a CNF expansion can be exponentially large.

However, the concept of NP-completenes is usually only applied to decision problems, where the expected answer is always in {yes,no}. One reason for this is exactly to avoid problems that are "hard" simply because the answer is large and there takes a lot of time to write.

So you cannot even speak about whether the problem is in NPC without first reformulating it such that its output is a single bit. (There are some well-known NP-complete problems that naturally seem to ask for more information -- such as the Traveling Salesman. But what one really proves is that the yes/no problem "is there an itinerary of length at most $N$?" is NP-complete).

Also, you seem to be committing a fallacy when you jump from "this is hard" to "it is probably NP-complete". Remember that there are two points to NP-completenes:

  • The problem must be hard enough, usually called "NP-hard", that is, there are polynomial reductions from every problem in NP -- usually shown by presenting a single reduction from another problem already known to be NP-hard.

  • At the same time, the problem must be easy enough, namely, it must be in NP. That is, there must be a nondeterminsitic machine that solves it in polynomial time. Or equivalently, there must be a set of "certificates" for problem instances whose answer is "yes" such that a purported certificate can be checked for correctness in polynomial time.

Your intuitive leap to "should be in NPC" appears to ignore the second test.

share|improve this answer
    
You are right I should formulate in the form of decision problems. However, the original problem that intrigues me is if you know you can convert in polynomial time any arbitrary formula into CNF, would P=NP? If the conversion process is hard enough, certainly there would be no poly-time conversion algorithm. Any thought? –  Jing Zhang Oct 7 '12 at 14:59
    
I'm not even sure what it would mean to convert arbitrarily formulas to CNF in polynomial time -- since there are known families of formulas that have no polynomially bounded CNF equivalent. –  Henning Makholm Oct 7 '12 at 19:06
    
Also, note that "hardness" is not a total order between problems. In particular, it is not the case that just because a problem is not in P, it has to be NP-hard. Assuming that P$\ne$NP, one can explicitly construct (by diagonalization) a subset of $\mathbb N$ that is neither in P nor NP-hard. –  Henning Makholm Oct 7 '12 at 19:08
add comment

There are various ways to convert formulas to CNF avoiding the exponential growth of your example.

Wikipedia's Conversion_into_CNF shows how to do that. A good reference is the Handbook of Satisfiability, Chapter 2, CNF Encodings.

share|improve this answer
1  
It should be noted that the way they avoid exponential growth is by finding the CNF for a non-equivalent, but equisatisfaiable, formula. –  Carl Mummert Nov 25 '13 at 13:03
add comment

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.