SAT solving
DRAT proof
Abbreviated DRAT
A common SAT proof format based on redundant clause additions.
Definition
DRAT proof
A DRAT proof is a sequence of clause additions and deletions used to certify an unsat result.
DRAT permits a broad redundancy condition, which makes proof production practical for many SAT solvers. A checker validates the sequence independently of the search heuristics.
01
Example
The final empty clause represents contradiction after the checker accepts all required additions.
02
Important distinction
DRAT checks the Boolean clause problem. If an SMT query was bit-blasted incorrectly, the DRAT proof does not repair that translation.
After reading this article, you should be able to
- Define DRAT in the sense used on this site.
- Identify which part of a SAT or SMT pipeline a DRAT proof can certify.