Hostname: page-component-7b7567c8c-2jgqx Total loading time: 0 Render date: 2026-11-19T11:01:35.547Z Has data issue: false hasContentIssue false

Lower bounds for cutting planes proofs with small coefficients

Published online by Cambridge University Press:  12 March 2014

Maria Bonet
Affiliation:
Department de Lenguajes y Systemas Informaticos, Edificio e Pau Gargallo 5, 08028 Barcelona, Spain, E-mail: bonet@goliat.upc.es
Toniann Pitassi
Affiliation:
Department of Computer Science, University of Arizona, Tucson, AZ 85721, USA, E-mail: toni@cs.arizona.edu
Ran Raz
Affiliation:
Department of Applied Math, Weizmann Institute, Rehovat 76100, Israel, E-mail: ranraz@wisdom.weizmann.ac.il

Abstract

We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution.

We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other.

Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable