The Strategy of Cramming

TitleThe Strategy of Cramming
Publication TypeReport
Year of Publication2001
AuthorsWos, L
Series TitleJ. Automated Reasoning
Date Published08/2001
Other NumbersANL/MCS-P898-0801
Abstract

Offered in this article is a new strategy, cramming, that can serve well in an attempt to answer an open question or in an attempt to find a shorter proof. Indeed, when the question can be answered by proving a conjunction, cramming can provide substantial assistance. The basis of the strategy rests with forcing so many steps of a subproof into the remainder of the proof that the desired answer is obtained. As for reduction in proof length, the literature shows that proof shortening (proof abridgment) was indeed of interest to some of the masters of logic, masters that include C. A. Meredith, A. Prior, and I. Thomas. The problem of proof shortening (as well as other aspects of simplification) is also central to the recent discovery by R. Thiele of Hilbert\'s twenty-fourth problem. Although that problem was not included in his 1900 Paris lecture (because he had not yet sufficiently formulated it), Hilbert stressed at various times in his life the importance of finding simpler proofs. Because a sharp reduction in proof length (of constructive proofs) is correlated with a significant reduction in the complexity of the object being constructed, the cramming strategy is relevant to circuit design and program synthesis. The most impressive success with the use of the cramming strategy concerns an abridgment of the Meredith-Prior abridging of the Lukasiewicz proof for his shortest single axiom for the implicational fragment of two-valued sentential (or classical propositional) calculus. In the context of answering open questions, the most satisfying examples to date concern the study of the right-group calculus and the study of the modal logic C5. Various challenges are offered here.

PDFhttp://www.mcs.anl.gov/papers/P898.ps.Z