The Phase Transition in Exact Cover

Vamsi Kalapala, Cris Moore

We study EC3, a variant of Exact Cover which is equivalent to Positive 1-in-3 SAT. Random instances of EC3 were recently used as benchmarks for simulations of an adiabatic quantum…