Should Algorithms for Random SAT and Max-SAT be Different?

Sixue Liu, Gerard de Melo

We analyze to what extent the random SAT and Max-SAT problems differ in their properties. Our findings suggest that for random $k$-CNF with ratio in a certain range, Max-SAT can be…