Exact solutions for diluted spin glasses and optimization problems

Details Exact solutions for diluted spin glasses and optimization problems Exact solutions for diluted spin glasses and optimization problems

2001-03-15

arxiv.org/abs/cond-mat/0103328v2

Phys. Rev. Lett. 87 (2001) 127209

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 pages, 1 figure, accepted for publication in PRL

Scientific paper

10.1103/PhysRevLett.87.127209

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking Ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same Ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p=3, \gamma_d=0.818 and \gamma_s=0.918 resp.), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (\gamma_c^{var}=4.396 and \gamma_c^{var}=2.149 resp.).

Affiliated with

Also associated with

No associations

Rating

Exact solutions for diluted spin glasses and optimization problems 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 Exact solutions for diluted spin glasses and optimization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact solutions for diluted spin glasses and optimization problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564992