2+p-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition

R. Monasson, R. Zecchina, S. Kirkpatrick +2

Heuristic methods for solution of problems in the NP-Complete class of decision problems often reach exact solutions, but fail badly at "phase boundaries", across which the decisio…