"Threshold Behavior in a Boolean Network-Based Algorithm for K-SAT"   Small Research Awards Seminar

10/24/2003: 10:30am - 12:00pm
11th Floor Large Conference Room

Abstract: Participants: Alejandro Bugacov, Kristina Lerman, Aram Galstyan. Boolean satisfiability (SAT) is the canonical NP-complete problem that plays an important role in AI and has many practical applications in Computer Science in general. Boolean networks (BN) are dynamical systems that have recently been proposed as an algorithm for solving SAT problems. We have carried out a detailed investigation of the dynamical properties of BN corresponding to random SAT problems of different size. We varied the problem size by changing the number of variables and the number of clauses in the Boolean formula. We show that dynamics of BN corresponding to 3SAT problems display a phase-transition-like behavior, although this transition occurs far below the well known phase transition in the computational complexity of random 3SAT. This phase transition does not appear to be connected to the transition between frozen and chaotic dynamics regimes of random BN.

Last updated: Mon Jun 19 17:44:06 2006