Trajectories in Phase Diagrams, Growth Processes, and Computational Complexity: How Search Algorithms Solve the 3-Satisfiability Problem

Abstract

Decision and optimization problems typically fall into one of two categories for any particular solving algorithm. The problem is either solved quickly (easy) or demands an impractically long computational effort (hard). Here we show that some characteristic parameters of problems can be tracked during a run of the algorithm defining a trajectory through the parameter space. Focusing on 3-satisfiability, a recognized representative of hard problems, we analyze trajectories generated by search algorithms. These trajectories can cross well-defined phases, corresponding to domains of easy or hard instances, and allow one to successfully predict the times of resolution.