Proof Size Comparison
A second question about proof complexity is whether a method is more efficient than another. Since the proof size depends on the formula, it is possible that one method can produce a short proof of a formula and only long proofs of another formula, while a second method can have exactly the opposite behavior. The assumptions of measuring the size of the proofs relative to the size of the formula and considering only the shortest proofs are also used in this context.
When comparing two proof methods, two outcomes are possible:
- for every proof of a formula produced using the first method, there is a proof of comparable size of the same formula produced by the second method;
- there exists a formula such that the first method can produce a short proof while all proofs obtained by the second method are consistently larger.
Several proofs of the second kind involve contradictory formulae expressing the negation of the pigeonhole principle, namely that pigeons can fit holes with no hole containing two or more pigeons.
Read more about this topic: Proof Complexity
Famous quotes containing the words proof, size and/or comparison:
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (1817–1862)
“Great causes are never tried on their merits; but the cause is reduced to particulars to suit the size of the partizans, and the contention is ever hottest on minor matters.”
—Ralph Waldo Emerson (1803–1882)
“Certainly there is not the fight recorded in Concord history, at least, if in the history of America, that will bear a moment’s comparison with this, whether for the numbers engaged in it, or for the patriotism and heroism displayed.”
—Henry David Thoreau (1817–1862)