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 proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“The obese is ... in a total delirium. For he is not only large, of a size opposed to normal morphology: he is larger than large. He no longer makes sense in some distinctive opposition, but in his excess, his redundancy.”
—Jean Baudrillard (b. 1929)
“We teach boys to be such men as we are. We do not teach them to aspire to be all they can. We do not give them a training as if we believed in their noble nature. We scarce educate their bodies. We do not train the eye and the hand. We exercise their understandings to the apprehension and comparison of some facts, to a skill in numbers, in words; we aim to make accountants, attorneys, engineers; but not to make able, earnest, great- hearted men.”
—Ralph Waldo Emerson (1803–1882)