Tractability of Cut-free Gentzen-type propositional calculus with permutation inference II

✍ Scribed by Noriko H. Arai

• Book ID: 104326561
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 114 KB
• Volume: 243
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00186-8

✦ Synopsis

In Arai (1996), we introduced a new inference rule called permutation to propositional calculus and showed that cut-free Gentzen system LK (GCNF) with permutation (1) satisÿes the feasible subformula property, and (2) proves pigeonhole principle and k-equipartition polynomially. In this paper, we survey more properties of our system. First, we prove that cut-free LK+permutation has polynomial size proofs for nonunique endnode principle, Bondy's theorem. Second, we remark the fact that permutation inference has an advantage over renaming inference in automated theorem proving, since GCNF+renaming does not always satisfy the feasible subformula property. Finally, we discuss on the relative e ciency of our system vs. Frege systems and show that Frege polynomially simulates GCNF+renaming if and only if Frege polynomially simulates extended Frege.