Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms

Details Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms

2000-12-11

arxiv.org/abs/cond-mat/0012191v1

Physics

Condensed Matter

Statistical Mechanics

37 RevTeX pages, 15 figures; submitted to Phys.Rev.E

Scientific paper

10.1007/s100510170101

The computational complexity of solving random 3-Satisfiability (3-SAT) problems is investigated. 3-SAT is a representative example of hard computational tasks; it consists in knowing whether a set of alpha N randomly drawn logical constraints involving N Boolean variables can be satisfied altogether or not. Widely used solving procedures, as the Davis-Putnam-Loveland-Logeman (DPLL) algorithm, perform a systematic search for a solution, through a sequence of trials and errors represented by a search tree. In the present study, we identify, using theory and numerical experiments, easy (size of the search tree scaling polynomially with N) and hard (exponential scaling) regimes as a function of the ratio alpha of constraints per variable. The typical complexity is explicitly calculated in the different regimes, in very good agreement with numerical simulations. Our theoretical approach is based on the analysis of the growth of the branches in the search tree under the operation of DPLL. On each branch, the initial 3-SAT problem is dynamically turned into a more generic 2+p-SAT problem, where p and 1-p are the fractions of constraints involving three and two variables respectively. The growth of each branch is monitored by the dynamical evolution of alpha and p and is represented by a trajectory in the static phase diagram of the random 2+p-SAT problem. Depending on whether or not the trajectories cross the boundary between phases, single branches or full trees are generated by DPLL, resulting in easy or hard resolutions.

Affiliated with

Also associated with

No associations

Rating

Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257497