Hi I'm new, my knowleg of english is not so good so I apologize about a error who probably I will do. Ok my question is: "what is the "n" of SAT Algorithm?". Let me explain, when I have a algorithm for solve SAT, which has complexity O(n^2), the n is number of propositions or their occurence? For example in CNF (p \/ q) /\ (p \/ (not q)) /\ ((not p) \/ q) /\ p /\ q: the n of hypothetical is 2 or 8? Someone told me that the answer is 2 but I thought, if the answer is 2 for find satisfiability of DNF we need an algorithm with NP complexity cause for know if a DNF is satisfiable or unsatisfiable we just need to know if exist a clause who don't have proposition and its negation, but for do it we can need to read completely the DNF and if we have DNF like this: (p1 /\ p2 /\ ... /\ pn /\ (not p1)) \/ (p1 /\ (all possible combinations with prop. p2-pn and its neagation) /\ (not p1)) we have DNF with 2^(n-1) clause if we do same thing with other "p" like: (p2 /\ p1 /\ p3 /\ ... /\ pn /\ (not p2)) and we concatenated these DNF we have 2^n clause whit (2^n)*(n+1) occurence and we can do it with all "p" and something similar with clause who don't have max number of proposition. Now if not mistaken, SAT of DNF is P problem, so I wrong only about the algorithm for he DNFs? or SAT of DNF is NP problem? Anyway if we do something similar to CNF and if I have nondeterministic Turing machine just for apply a solution of one proposition we need 2^n step (or (2^n)+(2^(n-1)) in case of p1 and p2) and this mean ((2^n)*n)+(2*(2^(n-1))) step for solve NP problem with nondeterministic Turing machine. Ok I hope despite my bad English my topic is understandable.

Complexity is always measured as a function of the length of the input.

Of course SAT of DNF is a P problem. Only one clause has to be true. CNF howevor is NP Complete. Get yourself a good algorithm book.

http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#2-satisfiability

Learn that stuff way back :P

Quote:Original post by alvaro
Complexity is always measured as a function of the length of the input.

Ok so in case of SAT we have to consider a length of CNF, and not only the number of variable in it, witch can repeat infinite time.

Quote:Original post by ibebrett
Of course SAT of DNF is a P problem. Only one clause has to be true. CNF howevor is NP Complete. Get yourself a good algorithm book.

Yes I wrote it about DNF cause I assumed to consider only number of variable for calc complexity and in case u have 2^(number of variable) clauses in wrons case u can need 2^n step only for find one clause satisfable.

Quote:Original post by force_of_will
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#2-satisfiability

Learn that stuff way back :P

Umh I should go to review the slide of "Logic Math", but I sense from what I read on this page and in its traslation (and in page of Teorem of Cook-Levin), that the complexity is based on number of occurence in CNF and not on number of variable.

Thanks all for information and answers :) .