Lesson plan
Resolution proof compression by splitting
In mathematical logic, proof compression by splitting is an algorithm that operates as a post-process on resolution proofs. It was proposed by Scott Cotton in his paper "Two Techniques for Minimizing Resolution Proof". The Splitting algorithm is based on the following observation: Given a proof of unsatisfiability \pi and a variable x , it is easy to re-arrange (split) the proof in a proof of x and a proof of \neg x and the recombination of these two proofs (by an additional resolution step) may result in a proof smaller than the original. Note that applying Splitting in a proof \pi using a variable x does not invalidates a latter application of the algorithm using a differente variable y . Actually, the method proposed by Cotton generates a sequence of proofs \pi_1 \pi_2 \ldots , where each proof \pi_{i+1} is the result of applying Splitting to \pi_i . During the construction of the sequence, if a proof \pi_j happens to be too large, \pi_{j+1} is set to be the smallest proof in \{\pi_1, \pi_2, \ldots, \pi_j\} . For achieving a better compression/time ratio, a heuristic for variable selection is desirable.…
Article summary
In mathematical logic, proof compression by splitting is an algorithm that operates as a post-process on resolution proofs. It was proposed by Scott Cotton in his paper "Two Techniques for Minimizing Resolution Proof". The Splitting algorithm is based on the following observation: Given a proof of unsatisfiability \pi and a variable x , it is easy to re-arrange (split) the proof in a proof of x and a proof of \neg x and the recombination of these two proofs (by an additional resolution step) may result in a proof smaller than the original. Note that applying Splitting in a proof \pi using a variable x does not invalidates a latter application of the algorithm using a differente variable y . Actually, the method proposed by Cotton generates a sequence of proofs \pi_1 \pi_2 \ldots , where each proof \pi_{i+1} is the result of applying Splitting to \pi_i . During the construction of the sequence, if a proof \pi_j happens to be too large, \pi_{j+1} is set to be the smallest proof in \{\pi_1, \pi_2, \ldots, \pi_j\} . For achieving a better compression/time ratio, a heuristic for variable selection is desirable.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.