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:
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“Learn to shrink yourself to the size of the company you are in. Take their tone, whatever it may be, and excell in it if you can; but never pretend to give the tone. A free conversation will no more bear a dictator than a free government will.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Away with the cant of “Measures, not men!”Mthe idle supposition that it is the harness and not the horses that draw the chariot along. No, Sir, if the comparison must be made, if the distinction must be taken, men are everything, measures comparatively nothing.”
—George Canning (1770–1827)