Analysis of Backtracking Procedures for Random Decision Problems
Simona Maria Cocco, Liat Ein‐Dor, Rémi Monasson · 2004
This chapter contains sections titled: Introduction Phase Diagram, Search Trajectories and the Easy SAT Phase Overview of Concepts Useful to DPLL Analysis Clause Populations: Flows, Averages and Fluctuations Average-case Analysis in the Absence of Backtracking Occurrence of Contradictions and Polynomial SAT Phase Analysis of the Search Tree Growth in the UNSAT Phase Numerical Experiments Parallel Growth Process and Markovian Evolution Matrix Generating Function and Large-size Scaling Interpretation inTerms of Growth Process Hard SAT Phase: Average Case and Fluctuations Mixed Branch and Tree Trajectories Distribution of Running Times Large Deviation Analysis of the First Branch in the Tree The Random Graph Coloring Problem Description of DPLL Algorithm for Coloring Coloring in the Absence of Backtracking Coloring in the Presence of Massive Backtracking Conclusions References