Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » arxiv » cond-mat/0506053

 Article overview


Pairs of SAT Assignments and Clustering in Random Boolean Formulae
Thierry Mora ; Marc Mezard ; Riccardo Zecchina ;
Date 2 Jun 2005
Subject Disordered Systems and Neural Networks; Computational Complexity | cond-mat.dis-nn cs.CC
AffiliationLPTMS), Marc Mezard (LPTMS), Riccardo Zecchina (ICTP
AbstractWe investigate geometrical properties of the random K-satisfiability problem. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where SAT assignments are grouped into well separated clusters. This confirms the validity of the clustering scenario which is at the heart of the recent heuristic analysis of satisfiability using statistical physics analysis (the cavity method), and its algorithmic counterpart (the survey propagation algorithm). Our method relies on the study of pairs of SAT-assignments at a fixed distance. It uses elementary probabilistic arguments (first and second moment methods), and might be useful in other problems of computational and physical interest where similar phenomena appear.
Source arXiv, cond-mat/0506053
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser claudebot






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica