|
I understood that DNF boolean satisfiability is in P. This article seems to say it's NP-Complete. Since I'm not 100% sure of this, I'm not going to edit the article, but maybe someone else knows the definitive answer?
- Strange, you are right. It is easy to see that it is in P; a formula in DNF is satisfiable iff there is a clause without a contradiction. And that can be checked in linear time. What is also strange is the claim that the proof of NP-completeness is rather simple. As an instructor I have taught that proof myself, and even I don't think it's easy. :-) I'm a bit time-pressed at the moment, but I will put this on my to-do list. -- Jan Hidders 17:26 Dec 6, 2002 (UTC)
3-sat vs 2-sat
3-sat is NPC and 2-sat is not, why is it so?
It becomes a little strange because it means that it is
not possible in polynomial time to convert from 3-sat to 2-sat
in general.
This seems to be a little mystery to me.
- There are formulas you can express in 3SAT that are not expressible in 2SAT. So it is not even possible in exponential time or, for that matter, in any time. Take for example the formula f = (X1 or X2 or X3). How would you express that with a conjunction of clauses with just 2 variables? The proof that this is not possible is fairly simple. -- Jan Hidders 20:36, 9 Jun 2004 (UTC)
Proof of NP-completeness
I cut a section giving a "proof" that SAT is NP-complete, which I give below. I cut this section because it isn't really a proof, hardly even an outline, and because it uses concepts not developed in this article, such as Boolean circuit. It looks to me as though the author of this material was following the presentation in Christos Papadimitriou's book Complexity Theory, which presents a way to encode problems in NP as Boolean circuits first and then proves Cook's theorem as a corollary. I think that in Wikipedia it is better to give a direct proof, so I gave one in the Cook's theorem article. Gdr 20:53, 2004 Jul 21 (UTC)
Proof of NP-completeness
We give here a sketch of the proof of NP-completeness. To prove that SAT is NP-complete we must show that
- SAT is in NP, and
- all other NP problems can be reduced to it in polynomial time.
First, notice that it is easy to verify a YES answer: simply plug in a given set of variable values and see if they make the expression true. Therefore the problem is in NP.
Next, consider an arbitrary problem X that is in NP. By definition, there must be an algorithm for checking certificates for YES answers to X in polynomial time. Given such an algorithm it is possible to construct a polynomial-time algorithm that, given the size of the certificate, constructs a boolean circuit that is polynomially large in the certificate size and decides whether its input is a binary encoding of a valid certificate or not. This circuit can then be transformed by another polynomial-time algorithm into an equivalent boolean formula that is still polynomially large in the certificate size. It then holds that this formula is satisfiable iff there is a valid certificate, which means that we have reduced the original problem to SAT.
|
