DEPARTMENT RESEARCH ACADEMICS PEOPLE NEWS
Rice Computer Science		SEARCH:
Rice University Department of Computer Science presents Xiaoxu Wang Master of Science Thesis Defense Abstract Analysis on the Assignment Landscape of 3-SAT Problems The complexity of random 3-SAT problems is one of the fundamental problems in computer science theory. 3-SAT problems shift from satisfiable to unsatisfiable at the crossover point, and show high complexity around it. All assignments in a random SAT instance constitute a landscape. Using the CUDD package and Image Computation method, we conduct some experiments on the assignment landscape and the solution set. The crossover point can be obtained from the analytical computation of the spin model in statistical physics. This thesis confirms the clustering behavior of the solution set, another important conclusion drawn from the statistical model. Our experimental results indicate that the solution set does break into several clusters when the density falls into a specific range. As the density grows, the number of clusters increases and peak at density 3.2. As the density keeps increasing, the number of clusters in the solution set drops and non-solution basins in the assignment landscape emerge. These non-solution basins can cause high complexity in search-based SAT solvers at the densities right below the crossover point. Friday, May 14 at 1:00 p.m. in DH 2014 Copyright 2000 Rice University site problems: www@cs.rice.edu --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---