Editing Entscheidungsproblem (section)

==Practical decision procedures==
Having practical decision procedures for classes of logical formulas is of considerable interest for [[program verification]] and circuit verification. Pure Boolean logical formulas are usually decided using [[Boolean satisfiability problem|SAT-solving]] techniques based on the [[DPLL algorithm]].

For more general decision problems of first-order theories, conjunctive formulas over linear real or rational arithmetic can be decided using the [[simplex algorithm]], formulas in linear integer arithmetic ([[Presburger arithmetic]]) can be decided using [[Cooper's algorithm]] or [[William Pugh (computer scientist)|William Pugh]]'s [[Omega test]]. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using [[satisfiability modulo theories|SMT-solving]] techniques, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of [[real closed field]]s, is decidable; this is the [[Tarski–Seidenberg theorem]], which has been implemented in computers by using the [[cylindrical algebraic decomposition]].