The Resolution Complexity of Random Constraint Satisfaction Problems
Speaker: | Mike Molloy |
---|---|
Affiliation: | University of Toronto |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Constraint
satisfaction
problems
(CSP's)
are
generalizations
of
CNF
boolean
formulas.
We
are
given
a
set
of
variables,
and
a
domain
of
values
that
the
variables
can
take.
Some
subsets
of
the
variables
have
"constraints"
which
restrict
the
value-assignments
that
can
be
made
to
those
variables.
A
problem
is
satisfiable
if
there
is
an
assignment
of
values
to
the
variables
which
does
not
violate
any
of
the
constraints.
Some
well-studied
special
cases
are
k-SAT,
graph
colourability
and
graph
homomorphism.
Random
instances
of
various
CSP's
appear
to
be
very
difficult
to
solve
in
practice.
Chvátal
and
Szemerédi
proved
a
theorem
explaining
this
for
the
case
of
random
3-SAT:
with
high
probability,
the
resolution
complexity
of
a
random
3-SAT
formula
with
a
linear
number
of
clauses
will
be
exponentially
high.
This
implies
an
exponential
lower
bound
on
the
running
time
of
any
resolution-based
algorithm
(such
as
Davis-Putnam
and
its
many
variants).
In this talk, we discuss a wide class of models of random constraint satisfaction problems. The main result is that we determine which models from this class will, with high probability, have exponentially high resolution complexity for any linear number of constraints.
This is joint work with Siu On Chan.