The Phase Transition in Exact Cover

Details The Phase Transition in Exact Cover The Phase Transition in Exact Cover

2005-08-04

arxiv.org/abs/cs/0508037v2

Computer Science

Computational Complexity

9 pages, 1 figure, 1 table

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Phase Transition in Exact Cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Phase Transition in Exact Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Phase Transition in Exact Cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614155