Abstract

Most automated theorem provers are clausal-form provers based on variants of resolutionrefutation. In my [1990], I described the theorem prover OSCAR that was based instead on natural deduction. Some limited evidence was given suggesting that OSCAR was suprisingly efficient. The evidence consisted of a handful of problems for which published data was available describing the performance of other theorem provers. This evidence was suggestive, but based upon too meager a comparison to be conclusive. The question remained, “How does natural deduction compare with resolution-refutation?” In the ensuing seven years, OSCAR has evolved in important ways, and other developments have made it possible to collect more accurate comparative data. Specifically, the creation of the TPTP library of problems for theorem provers,1 and the availability of important theorem provers on the world wide web, make objective comparisons easier. These developments recently inspired Geoff Sutcliffe, one of the founders of the TPTP library, to issue a challenge to OSCAR. At CADE-13, a competition was held for clausal-form theorem provers.2 Otter was one of the most successful contestants. In addition, Otter is able to handle problems stated in natural form (as opposed to clausal form), and Otter is readily available for different platforms.3 Sutcliffe selected 212 problems from the TPTP library, and suggested that OSCAR and Otter run these problems on the same hardware. This “Shootout at the ATP corral” took place, with the result that OSCAR was on the average 40 times faster than Otter. In addition, OSCAR was able to find proofs for 16 problems on which Otter failed, and Otter was able to find proofs for 3 problems on which OSCAR failed. Taking into account that Otter was written in C and OSCAR in LISP, the speed difference of the algorithms themselves could be as much as an order of magnitude greater. Apparently, natural deduction has some advantages over resolution-refutation..