Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering * Pattern Recognition * Image Processing * Artificial Intelligence * Robotics

Programming in Propositional Logic or Reductions: Back to the Roots (Satisfiability)

Hermann Stamm-Wilbrandt

In this paper, NP-complete and polynomial solvable problems are reduced to the SATISFIABILITY problem. We call this process "programming" in propositional logic. On the one hand, the programs (propositional formulas) derived by this process build a rich pool of easy and hard (non-random) formulas for SATISFIABILITY-solving heuristics. On the other hand, the implementations (programs) give rise to new heuristics for solving SATISFIABILITY.

Click here to obtain the full paper (PS, gzip, 77100 bytes, 24 pages)

webmaster@www.informatik.uni-bonn.de - 16.12.05