Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances

Ke Xu, Wei Li

This paper first analyzes the resolution complexity of two random CSP models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the thres…