[Proof Complexity] A note on semantic vs syntactic cutting planes

Massimo Lauria lauria at kth.se
Sun Mar 31 05:27:38 CEST 2013

Dear colleagues,

I just uploaded on my webpage a note about semantic/syntactic cutting planes by
by Yuval Filmus and myself.

Please let us know your comments, observations, questions or followup results.


TITLE: A separation between semantic and syntactic cutting planes

In this note we argue that semantic cutting planes refutations are
stronger than syntactic ones. In particular, we give a formula for
which any refutation in syntactic cutting planes requires exponential
length, while there is a polynomial length refutation in semantic
cutting planes. This means that syntactic cutting planes does not
p-simulate (nor simulate) semantic cutting planes.
We  also give  a pair  of  incompatible cutting  planes lines  which
require exponential length to be  refuted in syntactic cutting planes.

On my webpage (see "manuscript" section)

A direct link
Massimo Lauria
KTH Royal Institute of Technology
School of Computer Science and Communication
Osquars Backe 2, SE-100 44 Stockholm, Sweden
+46 (0) 73 8008 125 (Cell.)

More information about the Proof-Complexity mailing list