Re: SAT and NP-Completeness

Yaakov Davis wrote:
What are the exact cases on which the Boolean satisfiability problem
is proven to be NP-complete?

Does the expression has to be in CNF form?

The problem of boolean satisfiability is to find if there exists an assignment of values to a generic boolean expression such that the expression is true. Note that the key thing here is that it is a decision problem, with a YES or NO answer.

I think I have a polinomial algorithm for the following general case:

a & !b & (c | !g | (d & e & f & (!g | h | i | j)).

What's the "general case"? All I see is a specific case.

If it's true, does it mean that I've found a polinomial algorithm for
all NP-Complete problems?

Does it solve a *generic* (or at least 3-CNF) problem in polynomial time? Guessing what your general case is, the answer is `no.'

Wikipedia says that these criteria are sufficient to generate NP-completeness: <http://en.wikipedia.org/wiki/Schaefer's_dichotomy_theorem>
A set of Boolean operators O, when applied to a set of variables, produces instances that are always polynomial if any one of the following conditions holds for the operators of O:
1. all such operators result in true when all its arguments are true;
2. all such operators result in true when all its arguments are false;
3. all such operators are equivalent to a set of binary clauses;
4. all such operators are equivalent to a set of Horn clauses;
5. all such operators are equivalent to a set of dual-Horn clauses;
6. all such operators are equivalent to a set of affine formulae (e.g., x_1 \oplus \cdots \oplus x_n = true
.

Relevant Pages

  • Re: Evaluating Exceptions, Try Except and Try Finally
    ... > statement where expression returns a Boolean value. ... > clauses require nothing more than a space or carriage return between them. ... In a series of nested conditionals where there are ... > real code, the statement ...
    (alt.comp.lang.borland-delphi)
  • Re: What is known about Exclusive 2SAT
    ... >>> It is well known that the 2SAT problem can be solved in polynomial time. ... >>> (linear time with respect to the number of clauses). ... >>> but I wanted to see what is already known about X2SAT. ... if he has a proof that 1-in-2 SAT is NP-complete ...
    (sci.math)