indico  First event Previous event KTH/Nordita/SU seminar in Theoretical Physics [before December 2013] Next event Last event   | view:  |  manage export to personal scheduler  | 
user login 

 

Solution space in satisfiability problems
  KTH/Nordita/SU seminar in Theoretical Physics [before December 2013]

Wednesday 13 May 2009
from 11:00 to 12:00
at FA31
Speaker : Mikko Alava (Department of Applied Physics, HUT)
Abstract : (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.

Nordita  | Last modified 07 March 2015 09:19  |  HELP