Abstract

It has been maintained by Smullyan that the importance of cut-free proofs does not stem from cut elimination per se but rather from the fact that they satisfy the subformula property. In accordance with such a viewpoint in this paper we introduce analytic cut trees, a system from which cuts cannot be eliminated but satisfying the subformula property. Like tableaux analytic cut trees are a refutation system but unlike tableaux they have a single inference rule and several branch closure rules. The main advantage of analytic cut trees over tableaux is efficiency: while analytic cut trees can simulate tableaux with an increase in complexity by at most a constant factor, tableaux cannot polynomially simulate analytic cut trees. Indeed analytic cut trees are intrinsically more efficient than any cut-free system.