Interactive protocol certifies unsolvable logical problems faster

A Multi-Prover Interactive Protocol for Certification of Resolution Refutations

Logic in Computer Science

Summary

Sometimes, finding proof that a set of logical rules cannot all be true at the same time takes a long time, because the proof can be huge. The authors present a new method where a fast verifier interacts with several independent helpers to check these proofs quickly and with very few errors. This approach reduces the verification time dramatically for the verifier, even though the helpers need more time to prepare their answers. They also show how using just one helper can work under some assumptions and give an example implementation of their method.

What this means in practice

Authors

Philipp Czerner, Adrian Krauss, Josia Pietsch, Javier Esparza

Abstract

A resolution refutation of a SAT-formula $\varphi$ is an independently checkable certificate proving that $\varphi$ is unsatisfiable. However, the refutations of $\varphi$ can be exponentially larger than $\varphi$. So, a verifier needs worst-case exponential time in the size of $\varphi$ to check their correctness. We present ResCertify, an interactive probabilistic protocol in which the verifier interacts with multiple independent, untrusted provers (MIP) to check the refutation with very low probability of error. The verifier runs in linear time in the size of $\varphi$. The provers require time $\mathcal{O}(n \cdot |Φ|)$, where $Φ$ is the resolution refutation and $n$ is the number of variables of $\varphi$. If they can be trusted to act as a multilinear oracle on certain queries, a single prover suffices, and the runtime can be improved to $\mathcal{O}(|Φ|)$. Finally, while the focus of our work is theoretical, we also report on a proof-of-concept implementation of ResCertify.