drat

DRAT is a proof format used to certify unsatisfiability proofs produced by SAT solvers. It is an extension of earlier proof formats that adds support for clauses to be justified by a RAT-type reasoning while also allowing deletions of previously added clauses. The goal is to provide a verifiable certificate that a given conjunctive normal form (CNF) formula is unsatisfiable, enabling independent verification of solver results.

A DRAT proof consists of a sequence of operations. Each operation either adds a clause to the current formula or deletes a previously added clause. Added clauses must be justified by either a RAT (a form of logical entailment check) or by being a tautology, ensuring that the resulting formula remains sound. Deletions help keep the proof compact by removing lemmas that are no longer needed. A verifier can step through the entire sequence, confirming that the certificate is valid and that the final state demonstrates unsatisfiability.

Usage and tooling: DRAT proofs are widely used to certify unsatisfiability results in SAT competitions and in toolchains requiring verifiable certificates. Verification tools such as drat-trim and other DRAT checkers read a DRAT proof and confirm its correctness. The DRAT format has influenced related formats and remains a common choice for certificate generation in modern solvers.

Origins and impact: DRAT emerged in the early 2010s as a practical alternative to earlier proof formats, offering a balance between expressiveness and verifiability. By enabling deletions and RAT-based additions, it can produce compact proofs and strengthen trust in solver results, supporting reproducibility and independent validation in research and industry.

See also: SAT solver, satisfiability, CNF, DRUP, RAT, proof certificate, drat-trim, LRAT.