3 ms·
SAT solving is the subtle and time consuming part. A valid SAT proof certificate can be verified efficiently.
by zozbot234 4y ago
SAT solving is the subtle and time consuming part. A valid SAT proof certificate can be verified efficiently.
- Jweb_Guru 4y agoI'm referring to producing the certificate as the time-consuming part, not the verification time (I disagree that verification is not subtle, but I suppose that doesn't matter as there are verified verifiers). For example, many SAT solvers no longer attempt to provide "pure" resolution proofs because they are too expensive to produce, which restricts the kinds of techniques you see used in competition. In fact, producing certificates efficiently is an active research area, which wouldn't be the case if certificate production had negligible cost, e.g. see https://lmcs.episciences.org/9357/pdf https://lmcs.episciences.org/9357/pdf.
- xavxav 4y agoSAT comp gives you 5x the solving time to check your proof, which is indicative that checking isn’t so simple (though it is on paper)