Daily Archives: 10.05.2012

Visualization of SAT-Solvers The SAT problem — determining if a formula in proposition logic is satisfiable — is decidable because you can construct a truth table. If there are n atomic propositions, there are 2^n assignments, so this is not an efficient algorithm. An efficient algorithm for SAT would solve the P=NP? problem in the affirmative, which is unlikely. However, many interesting algorithms for SAT (called SAT Solvers) have proved to be very efficient in practice. The algorithms are generally based on the DPLL (David, Putnam, Logemann, Loveland) algorithm and add sophisticated search methods and heuristics. The Master’s thesis project … Read more