Maximally flexible solutions of a random $K$-satisfiability formula

Han Zhao, Hai-Jun Zhou

Random $K$-satisfiability ($K$-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The s…