CJTCS Volume 2008 Article 5

Volume 2008

Article 5

The phase transition in exact cover

Vamsi Kalapala
Department of Computer Science
University of New Mexico

and

Cris Moore
Department of Computer Science
University of New Mexico
and
Santa Fe Insitute

October 1, 2008

Abstract

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 transition from satisfiability to unsatisfiability when the ratio r of clauses to variables exceeds some treshold r* = 0.62 +- 0.01. Usong the method of differential equations, we show that iff r is less than or equal to 0.546, then with high probability a random instance of EC3 is satisfiable. Combined with previous results this limits the location of the treshold, assuming it exists, to the range 0.546 < r* < 0.644.

Preformatted versions of the article
- DVI (28,624 bytes)
- PostScript (242,187 bytes)
- PDF (126,883 bytes)
Source materials for custom formatting
- LaTeX (cj08-05.tex, (23,046 bytes) needs .eps files for figures, in this directory.
- Bibliography (cj08-05.bbl, 7,770 bytes)
- Parameter settings for custom formatting (cjropts.tex, 165 bytes)
- Self citation in BIBTeX (259 bytes)

DOI: 10.4086/cjtcs.2008.005

Volume 2008, Article 4
[back]

Volume 2008 [back]

Published articles