Jump to content
  • Advertisement
Sign in to follow this  
Shi1485

Complexity of SAT Algorithm

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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 :) .

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!