Trajectories in phase diagrams, growth processes, and computational complexity: How search algorithms solve the 3-satisfiability problem

The solving complexity of computational problems in search algorithms is discussed. Statistical physics is used to study the complexity of algorithms applied to hard combinatorial problems. The trajectories generated by search algorithms were analyzed by focusing on 3-satisfiability (SAT) problems. The branch trajectories were related to polynomial time computations in the SAT phase. In the unSAT region, three trajectories lead to exponential calculations. To minimize the length of calculations, trajectories were kept horizontal in the unSAT region.