Search Problems in the Decision Tree Model.
The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems.  An interesting connection of this model to the complexity of resolution proofs is also mentioned.
Introduction
Ramsey's theorem asserts that every graph on n vertices has either a complete graph or an
independent set of size 1log n. A natural search problem associated with this theorem is
to find such a subgraph. Many other problems, like the ones below, have a similar flavor:
Given an assignment of n pigeons into find two pigeons assigned to the
same hole. Given a k-chromatic graph and a coloring of its nodes with fewer than k colors,
find two neighbors which have the same color. Given an unsatisfiable 3-CNF formula and
an assignment to its variables, find a clause which is not satisfied.
How hard is it to solve such search problems? The answer depends of course on their
representation and the computational model. We assume that the input is encoded in binary,
and that we are only allowed to probe input bits. This gives the familiar Boolean decision tree
Princeton University and Eotvos Lor'and University Budapest
y Weizmann Institute. Part of this work was done while the author was at the IBM Almaden Research
Center.
z DIMACS center and Hebrew U. Jerusalem
x Princeton University and Hebrew U. Jerusalem
model, adapted to solving search problems rather than computing Boolean functions. We
study the relationship between the standard nondeterministic, probabilistic and deterministic
variants of this model, and discover that it is drastically different from the case of function
computation, where all three measures are polynomially related (see [2, 7, 19, 14]). In all the
examples listed above it is easy to guess and verify the solution; hence the nondeterministic
decision tree complexity is small (a constant or polylog). If the decision tree was computing
a function, this would imply that both the randomized and deterministic complexities are
small, by the fact that the deterministic complexity (and thus the randomized too) is at
most the square of the nondeterministic complexity [2, 7, 19]. It turns out that for search
problems these gaps can be arbitrary large.
Our investigation is partly motivated by a similar study of search problems in the communication
complexity setting in the work of Karchmer and Wigderson [11] and Raz and
[18], where a similar phenomenon occurs but not to the same extent. Another
study of search problems was carried out by Papadimitriou [15] where complexity classes
defined by search problems were investigated. Some of our examples are inspired by this
work and [8, 10].
The examples above may remind the readers of resolution proofs. Indeed, resolution
proofs viewed top down yield Boolean decision trees to the search problems above (this fact
seems to be folklore and is elaborated in the appendix).
Thus, the exponential length lower bounds on resolution proofs (see e.g. [4]) provide
linear deterministic lower bounds even when the nondeterministic complexity is a constant.
However, the distinction between the resolution and the decision tree points of view becomes
clear when trying to make sense out of the probabilistic model. In resolution, one proves
simultaneously that every assignment falsifies some clause in an unsatisfiable formula. This
has no natural probabilistic analog. The decision tree approach, where one must find for a
given input assignment a clause that it falsifies, has a natural randomized version. Indeed, we
will be primarily concerned with the power of probabilistic computation for such problems.
We prove that the probabilistic complexity can be at both ends of the spectrum. We give
an explicit search problem for which the probabilistic (and nondeterministic) complexity is
constant, but the deterministic is linear. On the other hand we provide two explicit problems
for which there is a large gap between the nondeterministic and probabilistic complexities:
one in which the first is constant and the second is
6 ), and another in which the first is
O(log n) while the second is nearly linear. Finally, we present an explicit problem for which
there is a simultaneous exponential gap between the nondeterministic versus the randomized
and the randomized versus the deterministic complexities. This last example uses an
upper bound due to Irani [9] on online coloring algorithms to provide a lower bound on the
deterministic complexity. We note here that as far as we know, no such simultaneous gaps
are known for any other model of computation.
The special case of nondeterministic complexity 2 deserves a special interest. It corresponds
to unsatisfiable 2-CNF formulae. We characterize the deterministic complexity by
the structure of the formula, and note that it can never exceed 1 log n. We show that
here too the gap between the randomized complexity and the nondeterministic, and the gap
between the randomized complexity and the deterministic can be arbitrarily large.
The paper is organized as follows; in section 2 we give the formal definitions of search
problems, decision trees and show that the CNF search problem is 'complete' for all the variants
of decision trees. In section 3 we construct search problems with a large gap between the
deterministic and the randomized complexity, randomized and nondeterministic complexity,
and simultaneous nondeterministic - randomized - deterministic complexity gaps. In section
4 we discuss the special case of nondeterministic complexity 2. The exact relationship to the
resolution problem appears in the appendix.
A search problem is specified by n variables and a collection of 'witnesses'. In addition, this
collection must have the property that every assignment to the n variables is associated with
at least one witness. Given an input string which is an assignment to the n variables, the
goal is to find a witness consistent with it. Formally,
Definition 2.1 A search problem on n variables is a relation F ' f0; 1g n \Theta W , such that
. W is a finite set, called the set of witnesses.
The goal of the search for input x 2 f0; 1g n ; is to find a w 2 W such that (x; w) 2 F , (we
call such a w a valid witness for x).
A special class of search problems come from DNF tautologies. A monomial m is a
conjunction of literals (over the variable set X). Let g be a DNF tautology with a set
of monomials M . That is, and so that g is true for every assignment to
the variables. g naturally defines a search problem on f0; 1g X \Theta M : Each input (a truth
assignment to the variables) is associated with all monomials that are satisfied by
it.
The class of search problems defined by DNF tautologies is quite general. Indeed as
we shall see, every search problem F gives rise to a search problem on an associated DNF
tautology, g(F ), that will turn out to be equivalent to F .
With every monomial m we associate the subcube Cm of all the points in f0; 1g X that
are consistent with m (i.e evaluate to '1' on m).
Definition 2.2 Let F ' f0; 1g n \Theta W be a search problem. The set of monomials associated
with F , denoted by M F is defined by m 2 M F if 9w 2 W such that 8x 2 Cm ; (x; w) 2 F .
In words, m 2 M F if all inputs x that are consistent with m share a mutual witness w.
2.1 Let F ' f0; 1g n \Theta W be a search problem and let g(F ) be the formula defined by
m, then g(F ) is a DNF tautology.
Proof: Every input x has a witness in W . Thus, in particular, the subcube that contains
the single point x defines a monomial F that is a witness for x in F 0 . 2
Thus g(F ) defines a valid DNF search problem F 0 ' f0; 1g n \Theta M F , where F 0 is the set
of pairs (x; m) such that x satisfies m. It will be convenient though, for historical reasons,
to consider f(F which is an unsatisfiable CNF formula with the associated search
problem: For each input (an assignment to the variables) find an unsatisfied clause. Observe
that there is a natural correspondence between witnesses of F and F 0 .
2.1 Decision tree complexity for search problems
Let F ' f0; 1g n \Theta W be a search problem. A deterministic decision tree for F is an algorithm
that may query the value of an input bit at each step. The goal is to find a consistent witness.
Formally, such an algorithm is a rooted binary tree in which every internal node is labeled by
a variable and the two outgoing edges are labeled by the two possible values to that variable.
Each leaf is labeled with a witness w 2 W . Every assignment of the variables determines a
path from the root to a leaf in a natural way. The tree is a valid decision tree, if for every
assignment this path ends in a leaf labeled by a valid witness.
The deterministic complexity of F , D(F ), is the minimum depth of any decision tree for
F .
The nondeterministic complexity of F , N(F ), is the minimum number of variables that
must be probed in order to find a valid witness for the worst case input. Alternatively, it is
exactly the maximum size, over all inputs x, of the smallest monomial in M F that is satisfied
by x.
A randomized decision tree for F is a distribution over deterministic decision trees for F .
The complexity of a randomized decision tree is the expected path length for the worst case
input. The randomized complexity of F , R(F ), is the minimum over all randomized decision
trees for F .
Facts:
1. Let F ' f0; 1g n \Theta W be a search problem and F 0 ' f0; 1g n \Theta M F the associated search
problem. Then D(F
there is a natural correspondence between any decision tree for F (deterministic, randomized
or nondeterministic) and a (corresponding) decision tree for F 0 . Thus F and
F 0 are indeed restatement of essentially the same problem. Throughout the paper we
will not distinguish between F and its associated F 0 .
2. For every decision problem F
An observation of Chvatal and Szemer'edi [5] is that for a search problem F , lower bounds
on the (regular) resolution process for the unsatisfiable formula f(F ) imply lower bounds on
the deterministic decision tree complexity for F . We elaborate on that point in the appendix.
3 The relative power of determinism and randomization
versus non-determinism
In this section we present some explicit search problems for which there are large gaps
between the different decision tree complexity measures. Our main task is to construct
search problems for which N(F ) !! D(F
simultaneously. Another parameter to consider in each case is D(F ) versus the number of
variables n, which is the obvious upper bound for all the three measures of complexity.
3.1 Gaps between R(F) and D(F)
We present here an explicit search problem for which R(F
that the existence of such a problem follows from [4] by probabilistic arguments.
Let G(U; V; E) be a bipartite graph. Define the search problem DEG(G) on jEj variables
in the following way. Each 0-1 assignment to the variables is interpreted as a subgraph G 0
of G, defined by those edges that are assigned '1'. The search problem is to find a vertex
r whose degree in G 0 is not one. Clearly if the sides of the graph are not equal (jV j 6= jU
such a vertex exists for every subgraph G 0 , thus as long as the sides are not equal, DEG(G)
is a valid search problem.
Lemma 3.1 E) a bipartite graph with with maximum degree d and jU
Proof: The nondeterministic complexity, N(DEG(G))  d since for every input (subgraph
must only check the incident edges of the guessed vertex.
Consider the following random decision tree. Pick at random a vertex u 2 U and independently
a vertex edges that are incident to each of the two vertices (i.e 2d
edges are being checked). If u or v produce a witness stop, otherwise repeat this process
until done.
We claim that the probability that a witness is discovered in each iteration is at leastd+1 : If there are more than 2nd
d+1 edges in the subgraph G 0 defined by the '1'-edges, then at
least n
d+1 of the vertices in V are of degree at least 2. In this case the fact that v 2 V is
chosen at random proves the claim. If, on the other hand, G 0 has less than 2nd
d+1 edges, then
at least 2n
d+1 of the vertices in U are of degree 0 in G 0 . Thus, the fact that u 2 U is chosen at
random proves the claim in this case. We conclude that the expected number of iterations
in each of them 2d edges are probed which yields the above upper bound. 2
We will show now an infinite sequence of bipartite graphs for which the deterministic
complexity is \Omega\Gamma n).
E) be a bipartite graph with maximum degree d, jU
as before, and with the additional 'expansion' property: For every S ae U; jSj  n=4 )
Such a graph exists for large enough d and infinitely many n 0 s and can be efficiently
constructed using expander graphs [13] (d can be taken to be 30).
Theorem 3.1 Let G be a graph as defined above then
n).
Proof: The fact that already proved in Lemma 3.1.
We show an adversary strategy that is going to cause any deterministic decision tree to
probe
n) edges. The adversary will be limited to produce a subgraph for which 8v 2
(u)  1. Thus, the answer the decision tree has to find is
a vertex in U .
We need some definitions. For any S ' U and subgraph G 0 of G; NG 0
Sg. For stage i (after i edges were probed)
assigned '0' g
was not probed and 9e assigned '1' and e " e 0 6= ;g. Define G
In words, G i contains all the edges that are still possible for the adversary
to use in its final subgraph without violating the above limitation.
For each S ' U , define N
(S). For any subgraph G 0 of G, define S ae U to be
unmatchable if NG 0
denote a minimum cardinality unmatchable set in G 0 .
Finally call S
a minimal unmatchable set in step i.
By the above limitation on the adversary, at step i the subgraph G i contains a partial
matching from U to V . The decision tree cannot know the answer as long as there is no
isolated vertex in G i . Obviously such a vertex is, by itself, a minimum unmatchable set.
Initially, by the definition of the graph, jS
n=4. The strategy of the adversary is to make
sure that the minimum unmatchable set size does not decrease too fast. Formally, in step i
an edge probed. The adversary computes
the minimum unmatchable set that occurs on '0' answer on e.
2. not probed and x 2 Ug), i.e the minimum
unmatchable set that occurs on '1' answer on e.
He then chooses the answer on e so as to make S
i+1 the larger of S 0
The heart of the argument is the following claim.
Claim: If jS
there is a minimal unmatchable set S
i with jS
Proof: (of the claim) Assume e is asked in step i + 1. By the above strategy, jS
It is easy to see that cannot be matched into
V in G i . Thus, S contains an unmatchable set for step i of cardinality no more than
We can now complete the proof of Theorem 3.1 by the following argument. At the
beginning jS
n=4, at the end jS
and by the claim the cardinality of the minimal
unmatchable set does not decrease by more than a factor of 2. We conclude that at some
step j; n=16  jS
j. However, by the expansion property of G,
j. Since at each step, N i (S) can drop by at most d for any set S, at least
probed up to step j. 2
3.2 Gaps between N
In this section we construct two search problems for which the randomized complexity is
large while the nondeterministic complexity is small. The nondeterministic complexity of
the first problem is constant while its randomized complexity is
6 ). The second problem
has O(log n) nondeterministic complexity and its randomized complexity is \Omega\Gamma n= log n). The
proof of the lower bound on the randomized complexity of the first problem is by proving a
lower bound on the distributional complexity. (Yao [21] has shown that this is sufficient.)
The proof for the second is by an indirect reduction to a communication complexity game.
3.2.1 A problem with N(F
Let GRID be the following problem on variables. Consider an (m+ 1) \Theta (m+ 1)
matrix where the entry at the bottom left corner contains a one and the top row and rightmost
column are all zero. The n input bits determine the rest of the entries of the matrix.
For any 0-1 assignment to the rest of the matrix, the goal is to find an entry that is one
and its upper and right neighbors are zero. It is not hard to see that such a configuration
always exists.
This example is inspired by the lower bound argument of Hirsch, Papadimitriou and
Vavasis [8] for finding Brouwer fixed points and discussions with Noga Alon on extending it
to the random case.
Theorem 3.2
n).
Proof: The fact that clear. The theorem is established by the following
lemmata.
Lemma 3.2
Proof: A basic result of Yao [21] asserts that in order to prove lower bounds on randomized
decision tree complexity it is sufficient to show a distribution on the inputs such that any
deterministic algorithm requires a high expected number of queries. The distribution for
which we claim the lower bound is defined as follows: A random upward and rightward path
starting from the bottom left corner of the matrix and ending at the top row or right column
is picked uniformly from all such paths. The entries along the path receive the value '1' and
the rest receive the value '0'.
We claim that any deterministic algorithm
queries on the average
to discover the end point of the path, which is the only point where the desired
configuration occurs. We need the following claim.
be points in the matrix such that B is of Manhattan distance
at least d from A in the downward and left direction, and each of C is of
Manhattan distance at least d from B.
For the above distribution on paths, and 1  k
dthe probability that a path passes
through A given that it passes through B and avoids C k is at most 2
d
Proof (of the claim)
Let A be the event that the path passes through point A, B the event that it passes through
the event that it passes through C i .
d
d
d
are bounded by 1
d
since they correspond to max 1jd 0
).Let T be any deterministic decision tree for GRID. We will give additional information
to queries of T; At any stage i we provide T with a prefix of the path. Informally, the intuition
is the following, at each stage a contiguous initial segment of the path will be known to T .
If the next query is to a point of distance not too far from that known prefix, we provide T
with an additional segment of the path. A segment that is long enough to make sure that
knowing it will determine the value of the query. Thus, the conditional probability of future
queries will not depend on the answer to that query. If on the other hand, T queries a point
'far away' from the prefix of the path that he already know, then there is a good chance that
he will get a '0' answer and learn very little (by Claim 3.1).
Formally, at each stage i we provide T with the prefix of the path of length
with all the points on the path up to Manhattan distance 2=3 from the origin (the bottom
left corner). The length of the prefix is determined as follows: We start with
the ith stage '  0 is the largest number such that there exists a set of ' queries
so that for all 1  h  ' q h is to a point of distance D h with (j
2=3 from the origin, then we provide all the points on the path up to distance
(j to be j In such a case we say that contribute to j i .
Note that each query can contribute to q r for at most one r. It follows that for all i we have
that
Consider now what happens whenever an execution of T discovers the end point of the
path with less than 1m 1=3 steps. There must be the first step k for which the kth query is
at distance larger than (j answered '1'. Let B be the end point of the
prefix at stage k \Gamma 1 (i.e of distance j 2=3 from the origin), let A be the k-th query and
let all the previous queries that were answered by '0' and were to distance
further than (j 3.1, we have that for any 1  k  1=4m 1=3 the
probability that such an event will occur is at most 2
. Therefore the probability
that such an event will occur for some 1  k  1=4m 1=3 is at most 1=2 and therefore the
expected number of queries is at
2.
By replacing the grid with an expander we can get a problem with sharper bounds. Let
G be a 3-regular expander with n edges and let u be some node in G. Associate the n inputs
with the edges of G. Thus every assignment to the inputs defines a subgraph G 0 by the edges
that are assigned '1'. The problem ODD is: find a node other than u with an odd degree
in G 0 or find that u has even degree in G 0 .
ODD is a valid search problem by the fact that every graph has an even number of
nodes with odd degree. Therefore 3. Using the fact that expanders are rapidly
mixing, i.e. that a random walk in an expander gets to a node that is almost random after
O(log n) steps, we can show that R(ODD) is
3 ). The intuition is that as in the grid,
we concentrate the probability on walks of length n 2=3 that start from u. A query to a 'far
enough' point is unlikely to be on the walk, thus the tree would have to ask many vertices
along the walk in order to find its end. The advantage here is that 'far enough' becomes
quite small (O(log n) due to the mixing property).
We conjecture however that R(ODD) is \Theta(n).
Lemma 3.3
n)
Proof: There is a deterministic decision tree of complexity O(m) that solves the problem.
It asks all entries in the b mc-row. If there is any '1' entry, there must be an answer in the
upper half of the matrix. Otherwise, there must be an answer in the lower part of the matrix.
The decision tree probes next the relevant half of the b mc-column and recurses respectively.Lemma 3.4
Proof: There is a simple adversary strategy that can force any deterministic algorithm
to query at least locations. The adversary maintains a contiguous path of 1's from
the bottom left location (initially this path contains just the bottom left point). It also
maintains a direction for the path which is either horizontal or vertical. Given a query, if
it is not in the same row or column as the end point of the path or it is on the same row
(column) and the direction is vertical (horizontal), the adversary answers 0. If it is, say, in
the same row as the end point of the path and the direction is horizontal, then if in all the
columns between the end point and current query point a query has been made, then the
adversary answers 1 and gives away 1's for all the locations between the end point and query
point. If not, he answers the query by 0, finds the first column in which a query has not
been yet made, fills the row with 1's up to that point and switches the direction to vertical.
The other case is treated similarly.
It is easy to see that this strategy maintains the invariant that, at any step, the current
path can be augmented to the top row or right column. Moreover, the adversary answers 1
in a row (column) only if all columns (rows) between the current end point and the query
have points that had already been queried. So, every 1 in (i; j) position is discovered after
at least max(i;
3.2.2 A problem with N(F
Our next example is of nondeterministic complexity O(log n) and randomized complexity of
log n). The lower bound on the randomized complexity is based on a reduction from a
problem in communication complexity.
Let K 3m be the complete graph on 3m vertices. Let Pm be the set of all m-matchings in
K 3m i.e, the set of all m pairwise disjoint edges. Let Qm denote the set of all (m \Gamma 1)-subsets
of vertices of K 3m . Note that for every member p 2 Pm and every member q 2 Qm there is
an edge e 2 p such that e " Our search problem is essentially to find such an edge on
an input (p; q) 2 Pm \Theta Qm . However, we use some Boolean encoding of the problem.
We encode the sets by permutations (as explained below) and permutations by permutation
networks. A permutation network is a graph that 'realizes' permutations. Formally,
let G be a directed acyclic graph with k sources called input nodes, k sinks, called output
nodes and some other nodes called switches. Each input node has one out-going edge and
each output node has one in-going edge. Each switch has two in-going and two out-going
edges and can be assigned to select one of the two permutations that map the two in-going
edges to the two out-going edges. Clearly, a setting to each switch defines k paths in G, each
from an input node to an output node. Thus it defines a mapping from the k inputs to the
k outputs. It is easy to see that this mapping is always a permutation.
be the symmetric group on k elements. A graph G as above is called a 'k-
permutation network' if for every  2 S k there is a setting to the switches so that the
mapping defined by it is . For details of construction some permutation networks see
[12, 16].
Fact: For every k, a k-permutation network of size O(k log k) and depth O(log
be constructed efficiently. (e.g the shuffle-exchange network is a simple construction).
We can formally define now our n variables search problem MATCH: Let
Fix two disjoint k-permutation networks and let n be the total number of switches
O(m log m)). The input is an assignment to the switches of each network, interpreted as
two permutations elements. The first permutation encodes an m-matching p by;
is matched to  1 (i +m) for every 1  i  m. The second encodes a set q of size
by 1)g. The search problem is to find an edge as above.
Theorem 3.3
m) since all one has to do is to 'guess' i and find j; r such that
(this is an edge in p). In addition, check that j;
2 q by 'guessing'
This takes O(log m) probes.
The lower bound on the randomized complexity follows from: (i) the result of Raz and
Wigderson [18] on the complexity of the problem of finding the desired edge in the communication
complexity setting where one party has p 2 Pm as its input and the other party
has q 2 Qm as its input. They showed
bits must be transmitted. (ii) The fact
that any lower bound in the communication complexity model is also a lower bound in the
decision tree model, since the players can simulate the decision tree for each other (transmit
the current bit being probed). We don't give a detailed definition of the communication
complexity model here. For further information see [11], [18] and [1].
3.3 Simultaneous large gaps; N
In this section we construct a problem with simultaneous exponential gaps between N(F
and D(F ). We remark here that the deterministic lower bound is based on an interesting
application of an upper bounds for an online coloring algorithm.
Let r be an integer. Let E) be an m vertex graph that is not r colorable and
log r. The r-coloring search problem for G, denoted by COL r (G), is the following
variable problem: Every assignment of the log r variables is interpreted as an
r-coloring of G. The goal is to find two neighbors with the same color. Clearly such a
configuration always exists; we call such a configuration a 'monochromatic edge'.
Theorem 3.4 Let E) be a d-regular m-vertex
Ramanujan expander as constructed by Lubotzky, Phillips and Sarnak [13]. Then,
1. N(COL r
2. R(COL r
r) and R(COL r
3. D(COL r
Proof: We first have to show that the search problem is indeed valid, that is, to prove
that G is not r-colorable. This, as well as the rest of the proof will follow from the lemmata
below.
Lemma 3.5 For every r-coloring of G there exist at least 8 edges.
Proof: For a set S ' V let r be the color classes
under a coloring of V with r colors. The number of monochromatic edges is thus
However by the expansion properties of G, for every S 0 ae V; jE(S 0 )j  d\DeltajS
the number of monochromatic edges is at least
d
dm
d
mr
r
Lemma 3.6 R(COL r log r) and R(COL r
r).
Proof: The upper bound follows from Lemma 3.5: there are at least 8
edges for every r-coloring; thus selecting an edge at random and probing the 2 log r bits that
define its end points' colors results in a witness with probability at least 8mr=dm
2\Omega\Gamma4 =r).
Therefore we get that the expected number of queries is O(r log r).
The lower bound follows by showing a "hard" distribution (as in Yao [21]). The distribution
is uniform on all r-colorings. It is easy to see (by the 'birthday paradox'), that any
deterministic tree must probe at least
r vertices in order to hit the same color twice with
constant probability. (In particular to find two neighbors with the same color).
Lemma 3.7 Let m. For every integer s, every induced subgraph G 0 of G on at
most vertices has a vertex of degree at most s.
Proof: By [13] G has no cycles of length less than be the
smallest subgraph for which every vertex has degree at least s + 1. For a vertex v 2 G 0
g. Every u just one
neighbor in S i\Gamma1 and no neighbors in S i since otherwise G 0 has a cycle of length smaller than
2k. However, since the degree of every such u is at least s
for all which gives that G 0 contains at least s vertices. 2.
Lemma 3.8 D(COL r (G))
r. By Lemma 3.6 every induced subgraph G 0 of size at most
\Omega\Gamma/ 1p r ) has a vertex of degree of at most s. It follows that it can be online colored by
since Irani [9] has shown that the greedy algorithm has this performance.
This means that as long as the decision tree probes no more than t nodes, the adversary can
correctly online color the induced subgraph of the probed nodes so that no monochromatic
edge occurs. 2
4 The case of N
In this section we investigate decision problems for which N(F those which correspond
to unsatisfiable 2-CNF formulae. It turns out that in that case the situation is
different from the general case. Namely, D(F ) can be nearly characterized. It follows also
that for n-variables problems D(F n) for any such F . However, R(F ) may still be
small in comparison to D(F ).
Let f be an unsatisfiable CNF formula. We say that a sub formula f 0 of f is critical if it
is unsatisfiable but deletion of any clause makes it satisfiable.
Theorem 4.1 Let F be an n-variables search problem represented by a 2-CNF formula
be a critical sub formula with minimum number of clauses. Let k be the
number of variables in f 0 and m be the number of clauses in f 0 . Then k  m=2 and
log log m.
Proof: Let T be a decision tree for F . Look at the set of clauses in its leaves. Every input
reaches one of those clauses and falsifies it. So, the sub formula F 0 defined by the clauses of
the tree is unsatisfiable. i.e, it has at least m clauses. We conclude that the size of T is at
least m and its depth is at least log m which proves the lower bound on D(F ).
To prove the upper bound define for any unsatisfiable 2-CNF formula F the (standard)
directed graph G(F ), associated with is the set of 2n literals. For every clause
are edges in E(G(F )). For every single variable clause x;
is an edge of G(F ).
4.1 For any unsatisfiable 2-sat formula F let G(F ) be its graph, then there is a
variable x such that there is a directed path from x to x and a directed path from x to x in
Proof: The proof is by induction on the number of variables of F . The claim is easily
checked for 2 variables formulae. Assume F is unsatisfiable. Chose any variable x in F and
for any possible two clauses produce the 'resolvant' (y  z). The formula
obtained by deleting every clause that contains x or x and adding the new clauses is
unsatisfiable. By induction hypothesis there is some y such that G(F 1 ) has a path P 1 , from
y to y and a path P 2 , from y to y. However every edge (u; v) in G(F 1 ) is either an edge in
G(F ) or is the result of resolving two clauses of the form (x  u) and (x  v). But then, the
associated edges (u; x); (x; v) are a path from u to v in G(F ). Thus every path from a to b
in G(F 1 ) has a corresponding path from a to b in G(F ), in particular so do
Let f 0 be a critical sub formula of F and let G(f 0 ) be its associated directed graph. By
the claim there is a variable x for which there is a directed path P 1 from x to x and a directed
path P 2 from x to x. This leads to the following decision tree for F . First x is probed. If
the decision tree will find an edge in P 1 which is directed from '1' to '0' by binary
search along P 1 . If do the same thing on P 2 . Such an edge (u; v) corresponds
to a clause (u  v) which is falsified (since clause contributes two edges
to the graph so, the length of each of the paths is no more than 2m. We get the bound of
log m on the number of probes in the binary search.
We may take above to be simple paths, in particular the length of the paths is
bounded by k too. So, one gets an upper bound of 1 log k as well, and so k  m=2 by the
lower bound. 2
Corollary 4.1 For every 2-CNF search problem F on n variables, D(F 2.
We show now that the randomized complexity can be much smaller than the determin-
istic, and in other cases the largest possible.
Let G 1 be a constant degree Ramanujan expander on n vertices of the type constructed
by [13]. COL 2 (G) is the 2-coloring search problem as defined section 3.3.
Theorem 4.2
log n).
Proof: The fact that N(COL 2 (G 1 is clear from the definition of the problem. The
fact that G 1 is not two colorable and R(COL 2 (G 1 follows from the same arguments
as in the proof of 3.5, 3.6 with 2. The proof that D(COL 2 (G 1
log n) follows
from Theorem 4.1 above since a critical sub formula for COL 2 corresponds to the edges
of a non-two colorable subgraph of G 1 (in particular it must contain an odd cycle). However
the cycles of G 1 are of
length\Omega\Gammangt n) [13].
Let G 2 be an odd cycle of length n.
Theorem 4.3
n).
Proof obvious. Following Yao's technique, the distribution will be
uniformly concentrated on the n different inputs coloring, the i-th being the one that colors
correctly all edges except the i-th edge.
A deterministic tree of average depth d must have at least 1=2 of the inputs reaching
leaves of depth no more than 2d (from our special set of n inputs). Since there are no more
than 2 2d leaves of depth 2d, at least n
inputs arrive at the same leaf. However, no two
inputs from our special set can arrive at same leaf since every such input has a different
witness. So, n  2 2d+1 or d



--R

Complexity classes in communication complexity theory

Canonical expressions in Boolean algebra
Many hard examples for resolution

A computing procedure for quantification theory
robustness and the non-isomorphism of NP-complete sets
Exponential lower bound for finding Brouwer fixed points

Decision trees downward closure
Monotone circuits for connectivity require super- logarithmic depth
Introduction To Parallel Algorithms And Architectures: Arrays
Explicit expanders and the Ramanujan conjecture

graph theoretic lemmata and complexity classes
in Handbook Of Theoretical Computer Sci- ence
A machine-oriented logic based on the resolution principle
Monotone circuits for matching require linear depth
Query complexity
General purpose parallel architectures
Probabilistic computation
--TR

--CTR
Alexander Razborov , Avi Wigderson , Andrew Yao, Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.739-748, May 04-06, 1997, El Paso, Texas, United States
decision trees;boolean functions