On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.
An exponential lower bound for the size of tree-like cutting planes refutations of a certain family of conjunctive normal form (CNF) formulas with polynomial size resolution refutations is proved. This implies an exponential separation between the tree-like versions and the dag-like versions of resolution and cutting planes. In both cases only superpolynomial separations were known [A. Urquhart,  Bull. Symbolic Logic, 1 (1995), pp. 425--467; J. Johannsen,  Inform. Process. Lett., 67 (1998), pp. 37--41; P. Clote and A. Setzer, in  Proof Complexity and Feasible Arithmetics, Amer. Math. Soc., Providence, RI, 1998, pp. 93--117]. In order to prove these separations, the lower bounds on the depth of monotone circuits of Raz and McKenzie in [ Combinatorica, 19 (1999), pp. 403--435] are extended to monotone real circuits.An exponential separation is also proved between tree-like resolution and several refinements of resolution: negative resolution and regular resolution. Actually, this last separation also provides a separation between tree-like resolution and ordered  resolution, and thus the corresponding superpolynomial separation of [A. Urquhart,  Bull. Symbolic Logic, 1 (1995), pp. 425--467] is extended. Finally, an exponential separation between ordered resolution and unrestricted resolution (also negative resolution) is proved. Only a superpolynomial separation between ordered and unrestricted resolution was previously known [A. Goerdt, Ann. Math. Artificial Intelligence, 6 (1992), pp. 169--184].
Introduction
The motivation to work on the proof length of propositional proof systems is double. First, by the
work of Cook and Reckhow [15] we know that the claim that for every propositional proof system
there is a class of tautologies with no polynomial-size proofs is equivalent to NP 6= co-NP . This
connection explains the interest in developing combinatorial techniques to prove lower bounds for
dierent proof systems. The second motivation comes from the interest in studying eciency issues
in Automated Theorem Proving. The question is which proof systems have ecient algorithms
to nd proofs. Actually the proof system most widely used for implementations is resolution or
restrictions of resolution. Our work is relevant to both motivations. On one hand, all the separation
results of this paper improve to exponential the previously known superpolynomial ones. On the
other hand these exponential separations harden the known results showing ineciency of several
widely used strategies for nding proofs, especially for the resolution system.
A preliminary version of this paper appeared as [8] and as ECCC TR98-035.
y Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya,
fbonet,esteban,galesig@lsi.upc.es
z Partially supported by projects SPRIT 20244 ALCOM-IT, TIC 98-0410-C02-01 and PB98-0937-C04-03.
x Partially supported by project KOALA:DGICYT:PB95-0787.
{ Supported by an European Community grant under the TMR project.
k Institut fur Informatik, Ludwig-Maximilians-Universitat Munchen, jjohanns@informatik.uni-muenchen.de.
Research of this author done at Department of Mathematics, University of California, San Diego, supported by
DFG grant No. Jo 291/1-1.
Haken [21] was the rst in proving exponential lower bounds for unrestricted resolution. He
showed that the Pigeonhole Principle requires exponential-size resolution refutations. Later Urquhart
[35] found another class of tautologies with the same property. Chvatal and Szemeredi [11] showed
that in some sense, almost all classes of tautologies require exponential size resolution proofs (see
[4, 5] for simplied proofs of these results). These exponential lower bounds are bad news for
Automated Theorem Proving, since they mean that often the time used in nding proofs will be
exponentially long in the size of the tautology, just because the shortest proofs are also exponentially
long in the size of the tautology. A natural question then is what happens with the classes
of tautologies with polynomial-size proofs. Can we nd these proofs eciently? Several authors
[4, 12, 5] have given weakly exponential (in the minimal proof size) time algorithms for nding
resolution proofs. The question obviously is whether these results can be improved or not.
Formally, we say that a propositional proof system S is automatizable if there is an algorithm
that for every tautology F , nds a proof of F in S in time polynomial in the length of the shortest
proof of F in S. The only propositional proof systems that are known to be automatizable are
algebraic proof systems like Hilbert's Nullstellensatz [2] and Polynomial Calculus [12]. On the
other hand bounded-depth Frege proof systems are not automatizable, assuming factoring is hard
[29, 10, 7]. Since Frege systems and Extended Frege systems polynomially simulate bounded-depth
Frege systems, they are also not automatizable under the same assumptions.
Note that automatizability is equivalent to the approximability to within a polynomial factor of
the following optimization problem: Given a proof of some tautology, nd its minimal size proof .
Iwama [23] and Alekhnovich et al. [1] show that it is NP -hard to approximate this problem to
within a linear factor, for most of the commonly studied proof systems.
Many strategies for nding resolution proofs are described in the literature, see e.g. Schoning's
textbook [34]. One commonly used type of strategy is to reduce the search space by dening
restricted versions of resolution that are still complete. Such restricted forms are commonly referred
to as resolution renements. One particularly important resolution renement is tree-like
resolution. Its importance stems from the close relationship between the complexity of tree-like
resolution proofs and the runtime of a certain class of satisability testing algorithms, the so-called
Algorithms (cf. [31, 3]). We prove an exponential separation between tree-like resolution and
unrestricted resolution (Corollary 20), thus showing that nding tree-like resolution proofs is not
an ecient strategy for nding resolution proofs. Until now only superpolynomial separations were
known [36, 13].
In this paper, we consider three more of the most commonly used resolution renements: negative
resolution, regular resolution and ordered resolution. We show an exponential separation
between tree-like resolution and each one of the above restrictions (Corollary 20 for negative resolution
and Corollary 23 for both regular and ordered resolution). Goerdt [19, 18, 20] gave several
superpolynomial separations between unrestricted resolution and some renements, in particular
he gave a superpolynomial separation between ordered resolution and unrestricted resolution. We
improve this result by giving an exponential separation between ordered and negative resolution
(Corollary 28), thus showing that unrestricted resolution can have an exponential speed-up over
ordered resolution.
The Cutting Planes proof system, CP from now on, is a refutation system based on manipulating
integer linear inequalities. Exponential lower bounds for the size of CP refutations are already
proven. Impagliazzo et al. [22] proved exponential lower bounds for tree-like CP . Bonet et al. [9]
proved a lower bound for the subsystem CP  , where the coecients appearing in the inequalities
are polynomially bounded in the size of the formula being refuted. This is a very important result
because all known CP refutations fulll this property. Finally, Pudlak [30] and Cook and Haken
[14] gave general circuit complexity results from which exponential lower bounds for CP follow.
To this day it is still unknown whether CP is more powerful than CP  , i.e., whether it produces
shorter proofs or not.
Nothing is known about automatizability of CP proofs. Since there is an exponential speed-up
of CP over resolution, it would be nice to nd an ecient algorithm for nding CP proofs. A
question to ask is whether trying to nd tree-like CP proofs would be an ecient strategy for
nding Cutting Planes proofs. Johannsen [24] gave a superpolynomial separation, with a lower
bound of the
log n ), between tree-like CP and dag-like CP (this was previously known for
CP  from [9]). Here we improve that separation to exponential (Corollary 20). This means that
trying to nd tree-like proofs is also not a good strategy for nding proofs in CP .
1.1 Interpolation and Lower Bounds
Interpolation is a technique for proving lower bounds for resolution and Cutting Planes systems.
The name comes from a classical theorem of Mathematical Logic, the Craig's interpolation theorem.
Krajcek [27] reformulated this classical theorem in order to use it to prove lower bounds for proof
systems. Closely related ideas appeared previously in the mentioned works that gave lower bounds
for fragments of CP ([22, 9]).
The interpolation method translates proofs of certain formulas to circuits, preserving sizes. So
it is a way to reduce the problem of proving proof complexity lower bounds to circuit complexity
lower bounds. This is very important because in some cases there are strong circuit complexity
lower bounds. In particular for monotone circuits, there are both size and depth lower bounds.
The interpolation method works as follows. We consider a hard boolean function, i.e., one
that requires exponential size monotone circuits to be computed. We dene a contradiction
~r), such that A(~p; ~q) expresses that ~ p is a minterm 1 of the function (the variables ~q
describe the minterm), and B(~p; ~r) says that ~ p is a maxterm of the function (~r describes the max-
term). We suppose that A(~p; ~q) ^B(~p;~r) has a subexponential size refutation in a system with the
interpolation theorem (monotone version). Then by the theorem we can extract a subexponential
size monotone circuit that computes the hard function. Since this is impossible,
requires exponential size proofs.
With the above method we can prove lower bounds for resolution and CP  (see [9, 30, 27]).
But to get an exponential lower bound for full CP we actually need an interpolation theorem that
translates proofs into monotone real circuits [30]. See Section 3 for the denition of monotone real
circuits and Theorem 17 for the interpolation theorem for Cutting Planes.
The main body of this paper consists on exponential separations between tree-like and dag-like
(general) versions of two proof systems, resolution and Cutting Planes. So far we have outlined
the ideas in order to prove complexity lower bounds for systems like resolution and CP . In order
to separate the tree-like versions from the general versions of the proof systems, we need to dene
a contradiction that has polynomial size proofs in resolution and CP but for
which we can prove exponential size lower bounds for the corresponding tree-like versions.
The interpolation theorem applied on tree-like proofs gives rise to tree-like circuits (i.e., formu-
las). Therefore we need exponential size lower bounds for monotone formulas, or equivalently, we
need linear depth lower bounds for monotone circuits.
Karchmer and Wigderson [26] proved an O(log 2 n) lower bound on the depth of monotone
1 Recall that a minterm (respectively a maxterm) of a boolean function f : f0; 1g n ! f0; 1g is a set of inputs
such that for each y 2 f0; 1g n obtained from x by changing a bit
from 1 to 0 (respectively by changing a bit from 0 to 1) it holds that
circuits computing the st-connectivity function. Johannsen [24] extended this lower bound to real
circuits, and using the interpolation theorem he proved a superpolynomial separation between
tree-like and dag-like CP .
Lower bounds on the depth of monotone boolean circuits of the
order
were given by Raz and McKenzie [32]. Here we extend their results to the case of monotone real
circuits. Namely, we prove an
lower bound on the depth of monotone
real circuits computing a certain monotone function Gen n which is computable in polynomial
time. This implies an
lower bound on the size of monotone real formulas computing Gen n .
Hence, by the interpolation theorem, we get the exponential separation of tree-like from dag-like
Cutting Planes. The same ideas also separate tree-like from dag-like resolution.
1.2 Section Description
The paper is organized as follows. In Section 2 we give the basic denitions of the proof systems
considered in the paper. In Section 3 we dene monotone real circuits, and prove the depth lower
bound for them. This is applied in Section 4 to prove the lower bounds for tree-like CP , giving
exponential separations of tree-like CP from CP , tree-like resolution from resolution as well as
from regular resolution, ordered resolution and negative resolution. Finally in Section 5 we prove
the exponential lower bound for ordered resolution, separating it from negative resolution. We
conclude by stating some open problems.
2 The Proof Systems
Resolution is a refutation proof system for CNF formulas, which are represented as sets of clauses,
i.e., disjunctions of literals. We identify clauses in which the same literals occur, multiple occurrences
and the order of appearance are disregarded. The only inference rule is the resolution
rule:
C _ D
The clause C _ D is called the resolvent , and we say that the variable x is eliminated in this
inference. A resolution refutation of some set  of clauses is a derivation of the empty clause from
using the above inference rule. Resolution is a sound and complete refutation system, i.e., a set
of clauses has a resolution refutation if and only if it is unsatisable.
Several renements of the resolution proof system, i.e., restricted forms that are still complete,
have appeared in the literature. In this paper we consider the following three:
1. The regular resolution system: Viewing the refutations as graph, in any path from the empty
clause to any initial clause, no variable is eliminated twice.
2. The ordered 2 resolution system: There exists an arbitrary ordering of the variables in the
formula being refuted, such that if a variable x is eliminated before a variable y on any path
from an initial clause to the empty clause, then x is before y in the ordering. As no variable
is eliminated twice on any path, ordered resolution is a restriction of regular resolution.
3. The negative resolution system (N-resolution for short): To apply the resolution rule, one of
the two clauses should consists only of negative literals.
In Goerdt's paper [18] and in the preliminary version [8] of this paper, this renement is called Davis-Putnam
resolution. In the meantime, we have learned that it is more commonly known as ordered resolution.
In a tree-like proof any line in the proof can be used only once as a premise. Should the same
line be used twice, it must be rederived. A proof system that only produces tree-like proofs is called
tree-like. Otherwise we will call it dag-like, or just skip the adjective. When nothing is said it is
understood that the system is dag-like.
There is an algorithm (see e.g. Urquhart [36]) that transforms a tree-like resolution proof into
a possibly smaller regular tree-like resolution proof. Therefore tree-like resolution proofs of minimal
size are regular. That means that under the viewpoint of proof system complexity, tree-like
resolution and tree-like regular resolution are polynomially equivalent.
The Cutting Planes proof system, CP for short, is a refutation system for CNF formulas,
as resolution. It works with linear inequalities. The initial clauses are transformed into linear
inequalities in the following way:
_
_
A CP refutation of a set E of inequalities is a derivation of 0  1 from the inequalities in E and
the axioms x  0 and x  1 for every variable x, using the CP rules which are basic algebraic
manipulations, additions of two inequalities, multiplication of an inequality by a positive integer
and the following division rule:
i2I a i x i  k
i2I
a i
where b is a positive integer that evenly divides all a i ,
It can be shown that a set of inequalities has a CP -refutation i it has no f0; 1g-solution.
Any assignment satisfying the original clauses is actually a f0; 1g-solution of the corresponding
inequalities, provided that we assign the numerical value 1 to True and the value 0 to False. It is
also well-known that CP can polynomially simulate resolution [16], and this simulation preserves
tree-like proofs.
3 Monotone Real Circuits
A monotone real circuit is a circuit of fan-in 2 computing with real numbers where every gate
computes a nondecreasing real function. This class of circuits was introduced by Pudlak [30]. We
require that monotone real circuits output 0 or 1 on every input of zeroes and ones only, so that
they are a generalization of monotone boolean circuits. The depth and size of a monotone real
circuit are dened as usual, and we call it a formula if every gate has fan-out at most 1.
Lower bounds on the size of monotone real circuits were given by Pudlak [30], Cook and Haken
[14] and Fu [17]. Rosenbloom [33] shows that they are strictly more powerful than monotone boolean
circuits, since every slice function can be computed by a linear size, logarithmic depth monotone
real circuit, whereas most slice functions require exponential size general boolean circuits. On the
other hand, Jukna [25] gives a general lower bound criterion for monotone real circuits, and uses
it to show that certain functions in P=poly require exponential size monotone real circuits. Hence
the computing power of monotone real circuits and general boolean circuits is incomparable.
For a monotone boolean function f , we denote by dR (f) the minimal depth of a monotone real
circuit computing f , and by s R (f) the minimal size of a monotone real formula computing f .
The method of proving lower bounds on the depth of monotone boolean circuits using communication
complexity was used by Karchmer and Wigderson [26] to give
an
n) lower bound
on the monotone depth of st-connectivity. Using the notion of real communication complexity introduced
by Krajcek [28], Johannsen [24] proved the same lower bound for monotone real circuits.
In the case of boolean circuits the Karchmer-Wigderson result was generalized by Raz and
McKenzie [32]. Consider the monotone function Gen n of n 3 inputs t a;b;c , 1  a; b; c  n is dened
as follows: for c  n, we dene the relation ' c (c is generated) recursively by
or there are a; b  n with ' a
Finally Gen n ( ~ From now on we will write a; b ' c for t
Raz and McKenzie [32] proved a lower bound of the
on the depth of
monotone boolean circuits computing Gen n . By a modication of their method we show that this
result also holds for monotone real circuits:
Theorem 1. For some  > 0 and suciently large n
dR (Gen n )
This section is dedicated entirely to the proof of the above theorem. In the next section (Section
we will see how to use the lower bounds provided by Theorem 1 to obtain lower bounds for the
complexity of proofs in resolution and Cutting Planes proof systems.
3.1 Real Communication Complexity
Let R  X  Y  Z be a multifunction, i.e. for every pair (x; y) 2 X  Y , there is a z 2 Z with
We view such a multifunction as a search problem, i.e., given input (x; y) 2 X  Y ,
the goal is to nd a z 2 Z such that (x;
A deterministic communication protocol P over XY Z species the exchange of information
bits between two players, I and II, that receive as inputs respectively x 2 X and y 2 Y and nally
agree on a value P (x; y) 2 Z such that (x; R. The deterministic communication
complexity of R, CC(R), is the number of bits communicated between players I and II in the
optimal protocol for R.
A real communication protocol over X  Y  Z is executed by two players I and II who
exchange information by simultaneously playing real numbers and then comparing them according
to the natural order of R. This generalizes ordinary deterministic communication protocols in the
following way: in order to communicate a bit, the sender plays this bit, while the receiver plays a
constant between 0 and 1, so that he can determine the value of the bit from the outcome of the
comparison.
Formally, such a protocol P is specied by a binary tree, where each internal node v is labeled
by two functions f I
giving player I's move, and f II
and each leaf is labeled by an element z 2 Z. On input (x; y) 2 X  Y , the players construct a
path through the tree according to the following rule:
At node v, if f I
(y), then the next node is the left son of v, otherwise the right
son of v.
The value P (x; y) computed by P on input (x; y) is the label of the leaf reached by this path.
A real communication protocol P solves a search problem R  X  Y  Z if for every (x; y) 2
holds. The real communication complexity CCR (R) of a search problem
R is the minimal depth of a real communication protocol that solves R.
For a natural number n, let [n] denote the set be a monotone
boolean function, let X := f 1 (1) and Y := f 1 (0), and let the multifunction R f  X  Y  [n]
be dened by
The Karchmer-Wigderson game for f is dened as follows: Player I receives an input x 2 X and
Player II an input y 2 Y . They have to agree on a position i 2 [n] such that (x;
Sometimes we will say that R f is the Karchmer-Wigderson game for the function f . There is a
relation between the real communication complexity of R f and the depth of a monotone real circuit
or the size of a monotone real formula computing f , similar to the boolean case:
f be a monotone boolean function. Then
CCR (R f )  dR (f) and CCR (R f )  log 3=2 s R (f) :
For a proof see [28] or [24].
We will apply Lemma 2 to the boolean function Gen to prove a linear lower bound for dR (Gen)
and an exponential lower bound for s R (Gen), from a lower bound for CCR (R Gen ). It is immediate
to see that to establish Theorem 1 from Lemma 2, it suces to prove the following result:
Theorem 3. For some  > 0 and suciently large n
CCR (R Genn )
Analogously to the case of [32], to prove Theorem 3 we will prove a more general result about
real communication complexity. As in [32] we will introduce a class of special games, the DART
games, and the measure of structured communication complexity. In the next subsection we prove
that lower bounds for the real communication complexity of a relation R associated to a DART
game can can be obtained proving lower bounds for the structured communication complexity of
R (Theorem 4).
3.2 DART games and structured protocols
Raz and McKenzie [32] introduced a special kind of communication games, called DART games,
and a special class of communication protocols, the structured protocols, for solving them.
For is the set of communication games specied by a relation R
. I.e., the inputs for Player I are k-tuples of elements
. I.e., the inputs for Player II are k-tuples of binary colorings y i of [m].
For all The relation R  X  Y  Z dening the game only
depends on e i.e., we can describe R(x;
can be expressed as a DNF-Search-Problem, i.e., there exists a DNF-
tautology FR dened over the variables e k such that Z is the set of terms of FR , and
holds if and only if the term z is satised by the assignment (e
A structured protocol for a DART game is a communication protocol for solving the search
problem R, where player I gets input x 2 X, player II gets input y 2 Y , and in each round,
player I reveals the value x i for some i, and II replies with y i . The structured communication
complexity of R 2 DART(m; k), denoted by SC(R), is the minimal number of rounds in a structured
protocol solving R.
The main theorem of [32] showed that for suitable m and k, the deterministic communication
complexity of a DART game cannot be much smaller than that of a structured protocol. We shall
show the same for its real communication complexity. Obviously, a structured protocol solving R
in r rounds can be simulated by a real communication protocol solving R in r  (dlog me+1) rounds.
Conversely, we will prove that the following holds:
Theorem 4. Let m; k 2 N. For every relation R 2 DART(m; k), where m  k 14 ,
CCR (R)  SC(R)
The proof of this theorem is the main technical result of this section and we dedicate to it the
entire Subsection 3.3.
As a rst corollary to Theorem 4, we observe that for DART games, real communication protocols
are no more powerful than deterministic communication protocols.
Corollary 5. Let m; k 2 N. For R 2 DART(m;
Proof. CC(R)  CCR (R)  SC(R)
m)
CC(R)).
In the rest of this subsection we show how to obtain the proof of Theorem 3 using Theorem 4. For
g. Consider the communication game PyrGen(m; d)
dened as follows: We regard the indices as elements of Pyr d , so that the inputs for the two
players I and II in the PyrGen(m; d) game are respectively sequences of elements
and we picture these as laid out in a pyramidal form with (1; 1)
at the top and (d; j), 1  j  d and the bottom. The goal of the game is to nd either an element
colored 0 at the top of the pyramid, or an element colored 1 at the bottom of the pyramid, or an
element colored 1 with the two elements below it colored 0. That is we have to nd indices (i;
such that one of the following holds:
1.
2. y i;j
3.
Observe that, setting e search problem can be dened as a
DNF search problem given by the following DNF tautology:
_
_
1jd
e d;j
3 Observe that w.l.o.g. we can assume that both players know the structure of the protocol of the game. Hence
we can assume that at each round they both know what is the coordinate i of the inputs they have to talk about.
Therefore they have no need to transmit the index i of this coordinate.
Therefore, PyrGen(m; d) is a game in DART(m; d+1 ).
The following reduction shows that the real communication complexity of the game PyrGen(m; d)
is bounded by the real communication complexity of the Karchmer-Wigderson game for Gen n for
a suitable n. The proof is taken from [32], we include it because we will have to refer to some
details of it below.
2. Then
CCR (PyrGen(m; d))  CCR (R Genn
Proof. We prove that any protocol P solving the Karchmer-Wigderson game for Gen n can be used
to solve the PyrGen(m; d) game. From their respective inputs for the PyrGen(m; d) game, Player
I and II compute respectively a minterm and a maxterm 4 for Gen n and then apply the protocol
We interpret the elements between 2 and n 1 as triples (i; j; k), where (i;
Now player I computes from his input x : Pyr d ! [m] an input ~ t x to Gen n with Gen n ( ~ t x
by setting the following:
a 1;1 ; a 1;1 ' n
a i+1;j ; a i+1;j+1 ' a i;j for (i;
where a i;j := (i; j; x i;j ). This completely determines ~ t x .
Likewise Player II computes from his input y : Pyr d ! (2 [m] ) a coloring col of the elements
from [n] by setting From this, he computes an
input ~ t y by setting a; b ' c i it is not the case that Obviously
Gen
Playing the Karchmer-Wigderson game for Gen n now yields a triple (a; b; c) such that a; b ' c
in ~ t x and a; b 6' c in ~ t y . By denition of ~ t y , this means that
by denition of ~ t x one of the following cases must hold:
a d;j for some j  d. By denition of col, y d;j
. In this case, y 1;1
a i;j . Then we have y i;j
In either case, the players have solved PyrGen(m; d) without any additional communication.
A lower bound on the structured communication complexity of PyrGen(m; d) was proved in
[32]:
Lemma 7 (Raz/McKenzie [32]). SC(PyrGen(m; d))  d.
A proof of Theorem 3 therefore follows immediately from the above results:
4 Recall the denition of minterm and maxterm from footnote 1.
Proof of Theorem 3. Fix 28 . By Theorem 4 and Lemma 7, we get CCR (PyrGen(m; d))
d log m) . Recall that 2. Therefore Lemma 6 immediately implies the Theorem,
taking 1From our Theorem 3 we obtain consequences for monotone real circuits analogous to those
obtained in [32] for monotone boolean circuits.
Denition (Pyramidal Generation). Let ~ t be an input to Gen n . We say that n is generated
in a depth-d pyramidal fashion by ~ t if there is a mapping m : Pyr d ! [n] such that the following
hold (recall that a; b ' c means t
Observe that the reduction in the proof of Lemma 6 produces only inputs from Gen 1
n (1) which
have the additional property that n is generated in a depth-d pyramidal fashion. Hence we can
state the following strengthening of Theorem 1:
Corollary 8. Let n; d and  be as above. Every monotone real formula that outputs 1 on every
input to Gen n for which n is generated in a depth-d pyramidal fashion, and outputs 0 on all inputs
where Gen n is 0, has to be of
size
z n
The other consequences drawn from Theorem 4 and Lemma 7 in [32] apply to monotone real
circuits as well, e.g. we just state without proof the following result:
Theorem 9. There are constants 0 < ;
< 1 such that for every function d(n)  n  , there is
a family of monotone functions f that can be computed by monotone boolean
circuits of size n O(1) and depth d(n), but cannot be computed by monotone real circuits of depth
less than
d(n).
The method also gives a simpler proof of the lower bounds in [24], in the same way as [32]
simplies the lower bound of [26].
3.3 Proof of Theorem 4:
To prove Thm. 4, we rst need some combinatorial notions from [32] and some lemmas. Let
A  [m] k and 1  j  k. For x be the number of  2 [m] such that
A. Then we dene
The following lemmas about these notions were proved in [32]:
([32]). For every A 0  A and 1  j  k,
Lemma 11 ([32]). Let 0 <  < 1 be given. If for every 1  j  k, AV
every  > 0 there is A 0  A with jA 0 j  (1 )jAj and
In particular, setting
14 , we get
Corollary 12. If m  k 14 and for every 1  j  k, AV
14 , then there is A 0  A
with
14 .
This corollary is almost identical to the corresponding statement in [32]. Only the values of
and  have been slightly modied to improve the nal bound.
For a relation R 2 DART(m; k), A  X and B  Y , let CCR (R; A; B) be the real communication
complexity of R restricted to AB.
Denition
called an (; ; ')-game if the following conditions hold:
1. R 2 DART(m; k),
2. SC(R)  ',
3. jAj  2  jXj and jBj  2  jY j,
4. T
14 .
The following lemma and its proof are slightly dierent from the corresponding lemma in [32],
because we use the strong notion of real communication complexity where [32] use ordinary communication
complexity. The modication we apply is analogous to that introduced by Johannsen
[24] to improve the result of Karchmer and Wigderson [26] to the case of real communication
complexity. This modication will aect the proof of the rst point of the next lemma.
Lemma 13. For every
1. if for every 1  j  k, AV
14 , then there is an (+2; +1; ')-game (R
with
(R
2. if '  1 and for some 1  j  k, AV
14 , then there is an
(R
Proof of Lemma 13. For part 1, we rst show that CCR (R; A; B) > 0. Assume otherwise, then
there is a term z in the DNF tautology FR dening R that is satised for every (x; y) 2 A  B.
Therefore y j
denote the number of possible values of x j
in elements of A, then this implies that jBj  2 mk
. On the other hand, jBj  2 mk  , hence it
follows that
, which is a contradiction since   m 1
14 implies
14 .
Let an optimal real communication protocol solving R restricted to AB be given. For a 2 A
and b 2 B, let  a and  b be the real numbers played by I and II in the rst round on input a and
b, respectively. W.l.o.g. we can assume that these are jAj distinct real numbers.
Now consider a f0; 1g-matrix of size jAj  jBj with columns indexed by the  a and rows indexed
by the  b , both in increasing order, and where the entry in position ( a ;  b ) is 1 if  a >  b and 0
if  a   b . Thus this entry determines the outcome of the rst round, when these numbers are
played. It is now obvious that either the upper right quadrant or the lower left quadrant must form
a monochromatic rectangle.
Hence there are A   A and B 0  B with jA  j  1jAj and jB 0 j  1jBj such that R restricted to
can be solved by a protocol with one round fewer than the original protocol. By Lemma 10
(1), AV DEG j
14 for every 1  j  k, hence by Corollary 12 there is A 0  A  with
4 jAj and T
14 . Thus (R; A is an
For part 2 we proceed like in the proof of the corresponding lemma of [32], with the numbers
slightly adjusted. Assume without loss of generality that k is the coordinate for which
14 . Let R 0 and R 1 be the restrictions of R in which the k-th coordinate
xed to 0 and 1, respectively. Obviously, R 0 and R 1 are DART (m; k 1) relations,
and therefore at least one of SC(R 0 ) and SC(R 1 ) is at least k 1. Assume without loss of generality
that SC(R 0 )  k 1. We will prove that there are two sets A 0
such that the following properties hold:
14 (5)
(R
This means that there is a (+3 log m; +1; k 1)-game (R (R
CCR (R; A; B) and this proves part 2 of Lemma 13.
Given any set U  [m] consider the sets AU  [m] k 1 and BU  (f0; 1g m associated to the
set U by the following denition of [32]:
there is an u 2 U such that
there is a w 2 f0; 1g m such that
The following two claims can be proved exactly as the corresponding Claims of [32] and we omit
their proof.
14. For a random set U of size m 5
14 , with m  1000 14 , we have that
15. For a random set U of size m 5
14 , with m  1000 14 we have that
3
Moreover it is immediate to see that the same reduction used in Claim 6.3 of [32] also works
for the case of real communication complexity. Therefore we get:
16. For every set U  [m]
(R
Take a random set U which with probability greater than 1, satises both the properties of
14 and Claim 15, and dene A 0 := AU and B 0 := BU . This means that with probability at
least 1both A
Recall that jAj
and that, by hypothesis on Part 2 of the lemma
14 . Therefore we have that
This proves (3). For (4) observe that by Claim 15 we have
The property (5) follows directly from Lemma 10 (2), and nally (6) follows from Claim 16.
We nally end with the proof of Theorem 4 from Lemma 13.
Proof of Theorem 4. Let k 2 N, k  1000. We prove that for any ;
is such that
CCR (R; A; B)  '
log m4
Observe that by Denition of (; ; ')-game, when we have that
Therefore CCR (R; A; (R). Moreover the right side of Equation 7 reduces to '
493 m).
Since by the same Denition '  SC(R), for we get the claim of the theorem:
CCR (R)  SC(R)
m)
To prove Equation 7, we proceed by induction on '  1 and   m 1=7 . In the base case ' < 1
(that is
7 , the inequality (7) is trivial, since the right hand side gets negative
for large m. In the inductive step consider (R; A; B) be an (; ; ')-game, and assume that (7)
holds for all . For sake of contradiction, suppose that
CCR (R; A; B) < '
log m4 +. Then either for every 1  j  k, AV
14 , and
Lemma 13 gives an ( (R
(R
or for some 1  j  k, AV
14 , then Lemma 13 gives an (
game (R
(R
log m4
log
both contradicting the assumption.
4 Separation between tree-like and dag-like versions of Resolution
and Cutting Planes
Cutting Planes refutations are linked to monotone real circuits by the following interpolation theorem
due to Pudlak:
Theorem 17 (Pudlak [30]). Let ~ p; ~q; ~r be disjoint vectors of variables, and let A(~p; ~q) and B(~p; ~r)
be sets of inequalities in the indicated variables such that the variables ~ p either have only nonnegative
coecients in A(~p; ~q) or have only non-positive coecients in B(~p; ~r).
Suppose there is a CP refutation R of A(~p; ~q) [ B(~p; ~r). Then there is a monotone real circuit
C(~p) of size O(jRj) such that for any vector ~a 2 f0; 1g j~pj
Furthermore, if R is tree-like, then C(~p) is a monotone real formula.
In [30], only the relationship between resolution proof size and monotone real circuit size was
stated. The fact that C(~p) is a monotone real formula if R is tree-like is not part of the original
theorem, but can be directly obtained from the proof of the theorem in [30]. The reason is that
the underlying graphs of the refutation and the circuit are the same.
We now dene an unsatisable set of clauses related to the boolean function Gen n . Let n and d
be natural numbers whose values will be xed below. Recall that Pyr d := f (i; g.
For a given mapping m dening a pyramidal generation in the sense of the denition above, our
unsatisable set of clauses will be the conjunction of two CNF, Gen(~p; ~q) and Col(~p; ~r). The clauses
in Gen(~p; ~q) will encode the property that the inputs ~q dene a pyramidal generation, and therefore
Gen 1. The clauses in Col(~p; ~r) will say that that the inputs ~r dene a coloring, so that
Gen
More precisely: the variables p a;b;c for a; b; c 2 [n] represent the input to Gen n ; variables q i;j;a
for (i; d and a 2 [n] encode a pyramid, where the element a is assigned to the position (i;
by the mapping m : Pyr d ! [n]; the variables r a for a 2 [n] represent a coloring of the elements by
1 such that 1 is colored 0, n is colored 1 and the elements colored 0 are closed under generation.
The set Gen(~p; ~q) is given by (8) - (11), and Col(~p; ~r) by (12) - (14).
_
1an
q i;j;a for (i;
r a for a 2 [n] (12)
a for a 2 [n] (13)
r a _ r b _
r c for a; b; c 2 [n] (14)
If Gen( ~ t; ~q) is satisable for a xed vector ~ t 2 f0; 1g n 3
, then n is generated in a depth-d pyramidal
fashion, and if Col( ~ t; ~r) is satisable, then Gen( ~ the variables ~ p occur only positively
in Gen(~p; ~q) and only negatively in Col(~p; ~r), Theorem 17 is applicable, and the formula obtained
from this application satises the conditions of Corollary 8. Hence we can conclude:
Theorem 18. Every tree-like CP refutation of the clauses Gen(~p; ~q) [ Col(~p; ~r) has to be of sizen  ) , for some  > 0.
On the other hand, there are polynomial size dag-like resolution refutations of these clauses.
Theorem 19. There are (dag-like) resolution refutations of size n O(1) of the clauses Gen(~p; ~q) [
Proof. First we resolve clauses (9) and (12) to get
q d;j;c _
r c (15)
Now we want to derive
r c for every (i;
downward from d to 1. The induction base is just (15).
Now by induction we have
r a and
we resolve them against (14) to get
r c for 1  a; b; c  n and then resolve
them against (11) and get
for every 1  a; b  n. All of these are then resolved against two instances of (8), and we get the
desired  q i;j;c _  r c for every 1  c  n.
Finally, we have in particular
q 1;1;a _  r a for every 1  c  n. We resolve them with (13) and get
a;a;n for every 1  a  n. These are resolved with (10) to get
q 1;1;a for every 1  a  n.
Finally, this clause is resolved with another instance of (10) (the one with to get the
empty clause.
It is easy to check that the above refutation is an N-resolution refutation. The following corollary
is an easy consequence of the above theorems and known simulation results.
Corollary 20. The clauses Gen(~p; ~q) [ Col(~p; ~r) exponentially separate tree-like resolution from
dag-like resolution and (dag-like) N-resolution as well as tree-like Cutting Planes from dag-like
Cutting Planes.
The resolution refutation of Gen(~p; ~q) [ Col(~p; ~r) that appears in the proof of Theorem 19 is
not regular. We do not know whether Gen(~p; ~q) [ Col(~p; ~r) has polynomial size regular resolution
refutations. To obtain a separation between tree-like resolution and regular resolution we will
modify the clauses Col(~p; ~r).
4.1 Separation of tree-like CP from regular resolution
The clauses Col(~p; ~r) are modied (and the modication called RCol(~p;~r)), so that Gen(~p; ~q) [
allow small regular resolutions, but in such a way that the lower bound proof still applies.
We replace the variables r a by r a;i;D for a 2 [n], 1  i  d and D 2 fL; Rg, giving the coloring of
element a, with auxiliary indices i being a row in the pyramid and D distinguishing whether an
element is used as a left or right predecessor in the generation process.
The set RCol(~p;~r) is dened as follows:
r a;d;D for a 2 [n] and D 2 fL; Rg (16)
r a;i+1;L _ r b;i+1;R _
r a;i;D _ r a;i;
r a;i;D _ r a;j;D for 1
Due to the clauses (19) and (20), the variables r a;i;D are equivalent for all values of the auxiliary
indices D. Hence a satisfying assignment for RCol(~p;~r) still codes a coloring of [n] such that
elements a with are colored 0, the elements b with b; b ' n are colored 1, and the 0-colored
elements are closed under generation. Hence if RCol( ~ t; ~r) is satisable, then Gen( ~
Hence any interpolant for the clauses Gen(~p; ~q) [RCol(~p;~r) satises the assumptions of Corollary
8, and we can conclude
Theorem 21. Tree-like CP refutations of the clauses Gen(~p; ~q) [ RCol(~p;~r) have to be of sizen  ) .
On the other hand, we have the following upper bound on (dag-like) regular resolution refutations
of these clauses:
Theorem 22. There are (dag-like) regular resolution refutations of the clauses Gen(~p; ~q)[RCol(~p; ~r)
of size n O(1) .
Proof. First we resolve clauses (9) and (16) to get
q d;j;a _
r a;d;D (21)
Rg. Next we resolve (10) and (17) to get
for 1  a  n and D 2 fL; Rg. Finally, from (11) and (18) we obtain
Rg.
Now we want to derive
r a;i;D for every (i;
induction on i downward from d to 1. The induction base is just (21).
For the inductive step, resolve (23) against the clauses
q i+1;j;a _  r a;i+1;L and  q i+1;j+1;b _
which we have by induction, to give
q i+1;j;a _
r c;i;D
for every 1  a; b  n. All of these are then resolved against two instances of (8), and we get the
desired  q i;j;c _  r c;i;D .
Finally, we have in particular
r a;1;L , which we resolve against (22) to get
q 1;1;a for every
a  n. From these and an instance of(8) we get the empty clause.
Note that the refutation given in the proof of Theorem 22 is actually a ordered refutation: It
respects the following elimination order
r 1;d
Corollary 23. The clauses Gen(~p; ~q) [ RCol(~p;~r) exponentially separate the following proof sys-
tems: Tree-like resolution from regular and ordered resolution.
5 Lower bound for ordered resolutions
Goerdt [18] showed that ordered resolution is strictly weaker than unrestricted resolution, by giving
a superpolynomial lower bound (of the
order
log log n )) for ordered resolutions of a certain family
of clauses, which on the other hand has polynomial size unrestricted resolution refutations. In this
section we improve this separation to an exponential one, in fact, we give an exponential separation
of ordered resolution from N-resolution.
To simplify the exposition, we apply the method of [18] to a set of clauses SP n;m expressing a
combinatorial principle that we call the String-of-Pearls principle: From a bag of m pearls, which
are colored red and blue, n pearls are chosen and placed on a string. The string-of-pearls principle
SP n;m says that, if the rst pearl is red and the last one is blue, then there must be a blue pearl
next to a red pearl somewhere on the string.
SP n;m is given by an unsatisable set of clauses in variables p i;j and q j for
where p i;j is intended to say that pearl j is at position i on the string, and q j means that pearl j
is colored blue. The clauses forming SP n;m are:
_
These rst three sets of clauses express that there is a unique pearl at each position.
These last three sets of clauses express that the rst pearl is red, the last one is blue, and that
a pearl sitting next to a red pearl is also colored red. The clauses SP n;m are a modied and
simplied version of the clauses related to the st-connectivity problem that were introduced by
Clote and Setzer [13].
We shall modify the clauses SP n;m in such a way as to make small ordered resolution refutations
impossible, while still allowing for small unrestricted resolutions. The lower bound is then proved
by a bottleneck counting argument similar to that used in [18], which is based on the original
argument of Haken [21]. Note that the clauses (24) - (26) are similar to the clauses expressing the
Pigeonhole Principle, which makes the bottleneck counting technique applicable in our situation.
The set SP 0
n;m is obtained from SP n;m by adding additional literals to some of the clauses.
First, the clauses (27) and (29) for 1  i < nand j 0  nare replaced by
for every ' 2 [m], where ^{ := n
1. Similarly, the clauses (28) and (29) for n
replaced by
for every ' 2 [m], where now ^{ := 2j. All other clauses remain unchanged. The modied clauses
n;m do not have an intuitive combinatorial interpretation dierent from the meaning of the original
clauses SP n;m . The added literals only serve to make the clauses hard for ordered refutations.
The idea is that, for the clauses (30)-(33) to be used as one would use the original (27)-(29) in
a natural short, inductive proof (like the one given below), the additional literals
^{;' have to be
removed rst. The positions ^{ are chosen in such a way that this cannot be done in a manner
consistent with a global ordering of the variables.
Theorem 24. The clauses SP 0
n;m have negative resolution refutations of size O(nm 2 ).
Proof. We rst give a negative refutation of the clauses SP n;m , and then show how to modify them
for SP 0
n;m .
For every i 2 [n], we will derive the clauses p i;j !
[m] from SP n;m by a negative
resolution derivation. For these are the clauses (27) from SP n;m . Inductively, assume we
have derived p i;j and we want to derive p (i+1);j !
q j from these.
Consider the clauses (29) of the form p i;j
Using the inductive
assumption, we derive from these the clauses p i;j
that these are
negative clauses.
By a derivation of length m, we obtain p (i+1);j !
q j from these and the clause
SP n;m . The whole derivation is of length O(m), and we need m of them, giving a total length of
for the induction step.
We end up with a derivation of the clauses p n;j !
of length O(nm 2 ). In another m
steps we resolve these with the initial clauses (28), obtaining the singleton clauses
Finally we derive a contradiction from these and the clauses
Now we modify this refutation for the modied clauses SP 0
n;m . First, note that the original
clauses (27) can be obtained from (30) by a negative derivation of length m.
Next, we modify those places in the inductive step where the clauses (29) are used that have
been modied. First, we resolve the modied clauses (31) resp. (33) with the inductive assumption,
yielding the negative clauses
These are then resolved with the clause
after which we can continue as in
the original refutation.
In the places where the clauses (28) are used in the original refutation, we rst resolve (32) with
the clauses p n;j !
yielding
n;j , which can be resolved with
to get the singleton
clauses
n;j as in the original refutation.
In particular, there are polynomial size unrestricted resolution refutations of these clauses. The
next theorem gives a lower bound for ordered resolution refutations of these clauses.
Theorem 25. For suciently large n and m  9n, every ordered resolution refutation of the
clauses SP 0
n;m contains at least 2 n
clauses.
Proof. For sake of simplicity, let n be divisible by 8, say nm+m be the number
of variables, and let an ordering x of the variables be given, i.e., each x  is one of the
variables p i;j or q j . Let R be a ordered resolution refutation of SP 0
n;m respecting this elimination
ordering, i.e., on every path through R the variables are eliminated in the prescribed order. We
shall show that R contains at least k! dierent clauses, which is at least 2 n
8 (log n 5) for large n.
For a position i 2 [n] and   N , let S(i; ) be the set of those pearls j  2k such that p i;j is
among the rst  eliminated variables, i.e.,
be the unique position such that there is an index  0 with
In other words, i 0 is the rst position for which k of the variables p i 0 ;j with j  2k
are eliminated.
Let the elements of S(i enumerated in increasing order for definiteness
only, the order is irrelevant for the argument. For each 1    k, dene a position i
by
Note that i  is the position ^{ appearing in the added literals in the modied clauses (31) for
or (27), where in the rst case, respectively in the clauses (33) for
in the second case.
Further dene R  := [2k] n S(i  ;  0 ), i.e., R  is the set of those pearls j  2k for which the
variable eliminated later than any of the variables p i 0 ;j  for 1    k. Note that for all
by denition of i 0 .
Denition. A critical assignment is an assignment that satises all the clauses of SP 0
n;m except
for exactly one of the clauses (24). From a critical assignment , we dene the following data:
The unique position i  2 [n] such that (p i  ;j the gap of
.
A 1-1 mapping is the unique j 2 [m]
such that (p i;j
For every j 2 [m], we refer to the value (q j ) as the color of j, where we identify the value 0 with
red and 1 with blue.
A critical assignment  is called 0-critical, if the gap is i each
are colored blue (i.e., (q
are colored red (i.e., (q j 1
Note that the positions and the pearls thus the notion of 0-critical
assignment, only depend on the elimination order and not on the refutation R.
As in other bottleneck counting arguments, the lower bound will now be proved in two steps:
First, we show that there are many 0-critical assignments. Second, we will map each 0-critical
assignment  to a certain clause C  in R, and then show that not too many dierent assignments
can be mapped to the same clause C  , thus there must be many of the clauses C  .
The rst goal, showing there are many 0-critical assignments, is reached with the following
claim:
26. For every choice of pairwise distinct pearls b
is a 0-critical assignment  with m  (i
Proof of Claim 26. For those positions i such that m  (i) is not dened yet, i.e.
arbitrarily but consistently, i.e. choose an arbitrary 1-1
mapping from [n] n fi to [m] n fb g. This is always possible, since by
assumption m  9k.
Finally, color those pearls that are assigned to positions to the left of the gap red, and those
that are assigned to positions to the right of the gap blue, i.e., set (q m (i)
. The pearls are colored according to the requirement in the
denition of a 0-critical assignment. Note that this does not result in a con
ict even if some of the
are among the because the positions are always on the correct
side of the gap: if i 0  n, then k. The remaining
pearls can be colored arbitrarily.
Now we map 0-critical assignments to certain clauses in R. For a 0-critical assignment , let
C  be the rst clause in R such that  does not satisfy C  , and
occurs in C
This clause exists because  determines a path through R from the clause
to the empty
clause, such that  does not satisfy any clause on this path. The variables p i 0 ;j with j  2k are
eliminated along that path, and
are the rst among them in the elimination order.
27. Let  be a 0-critical assignment and '  := m  (i  ). Then for every 1    k, the
literal
occurs in C  .
Proof of Claim 27. Let  0 be the assignment dened by  0 (p
other variables x. As p i 0 ;j  does not occur in C  ,  0 does not satisfy C  either.
There is exactly one clause in SP 0
n;m that is not satised by  0 , depending on where the gap i 0
is, this clause is
The requirement for the coloring of the j  in the denition of a 0-critical assignment entails that
these clauses are not satised by  0 , and that all other clauses are satised by  0 .
In any case, the literal  p i  ;'  occurs in this clause, and there is a path through R leading from
the clause in question to C  , such that  0 does not satisfy any clause on that path. The variable
that is eliminated in the last inference on that path must be one of the p i 0 ;j  for 1    k, by
the denition of C  . Since '  2 R  , the variable p i  ;'  appears after p i 0 ;j  in the elimination order,
by the denition of R  . Therefore p i  ;'  cannot have been eliminated on that path, so
occurs in C  .
Finally we are ready to nish the proof of the theorem. Let ;  be two 0-critical assignments
such that '  := m  (i  so that (p i  ;'  27, the
literal
occurs in C  , therefore  satises C  , and hence C  6= C  .
By Claim 26, there are at least k! 0-critical assignments  that dier in at least one of the
values m  (i  ). Thus R contains at least k! distinct clauses of the form C  .
The following corollary is a direct consequence of Theorems 25 and 24.
Corollary 28. The clauses SP 0
exponentially separate ordered resolution from
unrestricted resolution and N-resolution.
A modication similar to the one that transforms SP n;m into SP 0
n;m can also be applied to the
clauses Gen(~p; ~q), yielding a set DPGen(~p; ~q). Then for the clauses DPGen(~p; ~q) [ Col(~p; ~r), an
exponential lower bound for ordered resolutions can be proved by the method of Theorem 25 (this
was presented in the conference version [8] of this paper). Also the N-resolution proofs of Theorem
19 can be modied for these clauses. Thus the clauses exponentially
separate ordered from negative resolution as well.
6 Open Problems
We would like to conclude by stating some open problems related to the topics of this paper.
1. For boolean circuits (monotone as well as general), circuit depth and formula size are essentially
the same complexity measure, as they are exponentially related by the well-known
Brent-Spira theorem. Is there an analogous theorem for monotone real circuits, i.e., is
every monotone function f? This would be implied by the converse
to Lemma 2, i.e., dR (f)  CCR (R f ). Does this hold for every monotone function
2. The separation between tree-like and dag-like resolution was recently improved to a strongly
exponential one, with a lower bound of the form 2 n= log n ([5, 6, 31]). Can we prove the same
strong separation between tree-like and dag-like CP ?
3. A solution for the previous problem would follow from a strongly exponential separation of
monotone real formula size from monotone circuit size. Such a strong separation is not even
known for monotone boolean circuits.
4. Can the superpolynomial separations of regular and negative resolution from unrestricted
resolution [19, 20] be improved to exponential as well? And is there an exponential speed-up
of regular over ordered resolution?

Acknowledgments

We would like to thank Ran Raz for reading a previous version of this work and discovering an
error, Andreas Goerdt for sending us copies of his papers, Sam Buss for helpful discussions and
nally Peter Clote for suggesting us to work on resolution separations.



--R

Minimum propositional proof length is NP-hard to linearly approximate



Short proofs are narrow


Exponential separations between restricted resolution and cutting planes proof systems.
Lower bounds for cutting planes proofs with small coe

Using the Groebner basis algorithm to

An exponential lower bound for the size of monotone real circuits.
The relative e

Lower bounds on sizes of cutting planes proofs for modular coloring principles.

Unrestricted resolution versus N-resolution
Regular resolution versus unrestricted resolution.
The intractability of resolution.
Upper and lower bounds for tree-like cutting planes proofs
Complexity of
Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
Combinatorics of monotone computations.
Monotone circuits for connectivity require super-logarithmic depth





Separation of the monotone NC hierarchy.
Monotone real circuits are more powerful than monotone boolean circuits.

Hard examples for resolution.
The complexity of propositional proofs.
--TR

--CTR
Juan Luis Esteban , Jacobo Torn, A combinatorial characterization of treelike resolution space, Information Processing Letters, v.87 n.6, p.295-300, September
Michael Alekhnovich , Jan Johannsen , Toniann Pitassi , Alasdair Urquhart, An exponential separation between regular and general resolution, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Maria Luisa Bonet , Nicola Galesi, Optimality of size-width tradeoffs for resolution, Computational Complexity, v.10 n.4, p.261-276, May 2002
Albert Atserias , Mara Luisa Bonet, On the automatizability of resolution and related propositional proof systems, Information and Computation, v.189 n.2, p.182-201, March 15, 2004
Paolo Liberatore, Complexity results on DPLL and resolution, ACM Transactions on Computational Logic (TOCL), v.7 n.1, p.84-107, January 2006
Jakob Nordstrm, Narrow proofs may be spacious: separating space and width in resolution, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Juan Luis Esteban , Nicola Galesi , Jochen Messner, On the complexity of resolution with bounded conjunctions, Theoretical Computer Science, v.321 n.2-3, p.347-370, August 2004
Robert Nieuwenhuis , Albert Oliveras , Cesare Tinelli, Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T), Journal of the ACM (JACM), v.53 n.6, p.937-977, November 2006
Henry Kautz , Bart Selman, The state of SAT, Discrete Applied Mathematics, v.155 n.12, p.1514-1524, June, 2007
resolution;proof complexity;cutting planes proof system;computational complexity;circuit complexity