Satisfiability Problem · Formal Verification and Proof Systems
Lesson 2
We don't know! The existence of short unsatisfiability certificates is a big open problem. It is the subject of a field called proof complexity theory.
For the curious 🤓
The unsatisfiability problem is co-NP-complete.