Welcome to the new Indico service!
KTH/Nordita/SU seminar in Theoretical Physics

Solution space in satisfiability problems

by Mikko Alava (HUT, Espoo, Finland)

FA31 ()


(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.