📑 Table of Contents▼

Chaff is an algorithm for solving instances of the Boolean satisfiability problem in programming. It was designed by researchers at Princeton University. The algorithm is an instance of the DPLL algorithm with a number of enhancements for efficient implementation.

Implementations

edit

Some available implementations of the algorithm in software are mChaff and zChaff, the latter one being the most widely known and used. zChaff was originally written by Dr. Lintao Zhang, hence the “z”. It is now maintained by researchers at Princeton University and available for download as both source code and binaries on Linux. zChaff is free for non-commercial use.

References

edit
  • M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, S. Malik. Chaff: Engineering an Efficient SAT Solver, 39th Design Automation Conference (DAC 2001), Las Vegas, ACM 2001.
  • Vizel, Y.; Weissenbacher, G.; Malik, S. (2015). "Boolean Satisfiability Solvers and Their Applications in Model Checking". Proceedings of the IEEE. 103 (11): 2021–2035. doi:10.1109/JPROC.2015.2455034. S2CID 10190144.
edit


Stub icon

This formal methods-related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Chaff (disambiguation)

aircraft or other targets Chaff algorithm, an algorithm for solving instances of the boolean satisfiability problem Chaffing and winnowing, a method in

List of algorithms

Constraint satisfaction AC-3 algorithm general algorithms for the constraint satisfaction Chaff algorithm: an algorithm for solving instances of the Boolean

Propositional logic

g., DPLL algorithm, 1962; Chaff algorithm, 2001) that are very fast for many useful cases. Recent work has extended the SAT solver algorithms to work with

DPLL algorithm

science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the satisfiability of propositional

SAT solver

based on the CDCL framework as of 2019. Well known implementations include Chaff and GRASP. Look-ahead solvers have especially strengthened reductions (going

Conflict-driven clause learning

In computer science, conflict-driven clause learning (CDCL) is an algorithm for solving the Boolean satisfiability problem (SAT). Given a Boolean formula

Track algorithm

A track algorithm is a radar and sonar performance enhancement strategy. Tracking algorithms provide the ability to predict future position of multiple

Ron Rivest

cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity