Practical Decision
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 SAT-solving techniques based on the DPLL algorithm. 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'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 SMT-solving technique, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed fields, is decidable, for instance using the cylindrical algebraic decomposition; unfortunately the complexity of that algorithm is excessive for most practical uses.
A leading scientific conference in this field is Computer Aided Verification.
Read more about this topic: Decision Problem
Famous quotes containing the words practical and/or decision:
“Whatever practical people may say, this world is, after all, absolutely governed by ideas, and very often by the wildest and most hypothetical ideas. It is a matter of the very greatest importance that our theories of things that seem a long way apart from our daily lives, should be as far as possible true, and as far as possible removed from error.”
—Thomas Henry Huxley (1825–95)
“How could a man be satisfied with a decision between such alternatives and under such circumstances? No more than he can be satisfied with his hat, which he’s chosen from among such shapes as the resources of the age offer him, wearing it at best with a resignation which is chiefly supported by comparison.”
—George Eliot [Mary Ann (or Marian)