(joint work with S. Seitz and P. Kaski)
Combinatorial optimization is a very recent
playground for statistical physics since many
ideas of glassy systems apply directly. A paradigm
of a computer science problem here is the question
of satisfiability, as to a logical clause can be
"satisfied" without contradiction by assigning
to the logical values a suitable set of values
(true/false). In the classical K-satisfiability
problem one can in fact distinguish a phase diagram,
where an increasing constraint density induces a
transition from a solvable region to one where
instances of K-SAT problems become "UNSAT" or
unsatisfiable. The interest of the physics community
was catalyzed once it was realized that these problems
can be directly translated into spin glass ones, and
finding a solution for an instance is seen to be
equivalent to finding a groundstate for a disorder
configuration. This has lead to a flurry of activity
with the main emphasis on predictions of the phase
diagram - whether the solution space is broken into
"clusters" of solutions - and on methods of solving
these problems such as "Survey Propagation" or focused
local algorithms. In this talk I discuss some recent
attempts to understand the actual solution space. We
have simulated diffusion processes on the zero-energy
manifold. This provides information on the local and
global structure of the solution space and furnishes
an interesting example of diffusion on a hypercube in
the presence of dynamically generated disorder.
