[Proof Complexity] New preprint

Sam Buss sbuss at ucsd.edu
Wed Feb 1 20:31:31 CET 2017

Dear colleagues,

A preliminary version of a paper

"Short Refutations for the Equivalence-Chain Principle for Constant-Depth

by Ramyaa and myself is now available online at
http://www.math.ucsd.edu/~sbuss/ResearchWeb/AndOrTrees/. Comments are

  Best regards, Sam

Abstract: We consider tautologies expressing equivalence-chain
properties in the spirit of Thapen and Krajicek, which
are candidates for exponentially separating
depth $k$ and depth $k+1$ Frege proof systems.
We formulate a special case where the initial
member of the equivalence chain is fully specified
and the equivalence-chain implications
are actually equivalences.  This special case is
shown to lead to polynomial size resolution refutations.
Thus it cannot be used for separating depth $k$ and
depth $k+1$ propositional systems.
We state some Hastad switching lemma conditions
that restrict the possible propositional proofs
in more general situations.

More information about the Proof-Complexity mailing list