# Complexity of SAT Algorithm

This topic is 3347 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
Complexity is always measured as a function of the length of the input.

##### Share on other sites
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.

##### Share on other sites
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#2-satisfiability

Learn that stuff way back :P

##### Share on other sites
Quote:
 Original post by alvaroComplexity 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 ibebrettOf 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_willhttp://en.wikipedia.org/wiki/Boolean_satisfiability_problem#2-satisfiabilityLearn 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 :) .

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5

• 11
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633723
• Total Posts
3013541
×