The Phase Transition in Exact Cover
| dc.creator | Kalapala, Vamsi | |
| dc.creator | Moore, Cris | |
| dc.date | 2005-08-04 | |
| dc.date | 2008-10-08 | |
| dc.date.accessioned | 2026-07-07T10:08:17Z | |
| dc.date.available | 2026-07-07T10:08:17Z | |
| dc.description | 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 algorithm. Empirical results suggest that EC3 has a phase transition from satisfiability to unsatisfiability when the number of clauses per variable r exceeds some threshold r* ~= 0.62 +- 0.01. Using the method of differential equations, we show that if r <= 0.546 w.h.p. a random instance of EC3 is satisfiable. Combined with previous results this limits the location of the threshold, if it exists, to the range 0.546 < r* < 0.644. | |
| dc.description | 9 pages, 1 figure, 1 table | |
| dc.identifier | https://arxiv.org/abs/cs/0508037 | |
| dc.identifier | http://arxiv.org/abs/cs/0508037 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/170943 | |
| dc.subject | Computational Complexity | |
| dc.title | The Phase Transition in Exact Cover | |
| dc.type | text |