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:
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“Crotchless trouser allows wearer to show private parts in public. Neoprene-coated nylon pack cloth is stain resistant, water repellent and tickles thighs when walking. Tan-olive shade goes with most fetishes. Adjustable straps attach to belt for good fit and easy up-down. Pant is suitable for fast exposures as well as extended engagements. One size fits all.”
—Alfred Gingold, U.S. humorist. Items From Our Catalogue, “Flasher’s Pants,” Avon Books (1982)
“Most parents aren’t even aware of how often they compare their children. . . . Comparisons carry the suggestion that specific conditions exist for parental love and acceptance. Thus, even when one child comes out on top in a comparison she is left feeling uneasy about the tenuousness of her position and the possibility of faring less well in the next comparison.”
—Marianne E. Neifert (20th century)