Cutting planes, connectivity, and threshold logic

Archive for Mathematical Logic 35 (1):33-62 (1996)
  Copy   BIBTEX

Abstract

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP q ofCP, forq≥2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP 2-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE +, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,635

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Some Remarks on Lengths of Propositional Proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
A Note on Propositional Proof Complexity of Some Ramsey-Type Statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Uniqueness of Normal Proofs in Implicational Intuitionistic Logic.Takahito Aoto - 1999 - Journal of Logic, Language and Information 8 (2):217-242.

Analytics

Added to PP
2013-11-23

Downloads
48 (#242,282)

6 months
1 (#419,510)

Historical graph of downloads
How can I increase my downloads?