• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

穷举法揭示了随机3可满足性问题中的聚类和冻结现象。

Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem.

作者信息

Ardelius John, Zdeborová Lenka

机构信息

Swedish Institute of Computer Science, Kista, Sweden.

出版信息

Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 1):040101. doi: 10.1103/PhysRevE.78.040101. Epub 2008 Oct 2.

DOI:10.1103/PhysRevE.78.040101
PMID:18999364
Abstract

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions, which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.

摘要

我们研究随机3可满足性问题完整解集的几何性质。我们表明，即使对于中等规模的系统，簇的数量与理论渐近预测惊人地吻合。我们确定了解空间中的冻结转变，据推测这与解释随机约束满足问题中计算难度的起始有关。

相似文献

1
Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem.穷举法揭示了随机3可满足性问题中的聚类和冻结现象。
Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 1):040101. doi: 10.1103/PhysRevE.78.040101. Epub 2008 Oct 2.
2
Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains.具有增长域的随机约束满足问题的分析与置信传播研究
Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Jan;85(1 Pt 2):016106. doi: 10.1103/PhysRevE.85.016106. Epub 2012 Jan 10.
3
Entropy landscape and non-Gibbs solutions in constraint satisfaction problems.约束满足问题中的熵景观与非吉布斯解
Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Mar;77(3 Pt 1):031118. doi: 10.1103/PhysRevE.77.031118. Epub 2008 Mar 17.
4
Communities of solutions in single solution clusters of a random K-satisfiability formula.随机K可满足性公式单解簇中的解群落
Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Dec;80(6 Pt 2):066108. doi: 10.1103/PhysRevE.80.066108. Epub 2009 Dec 9.
5
Order-to-chaos transition in the hardness of random Boolean satisfiability problems.随机布尔可满足性问题硬度中的从有序到混沌的转变。
Phys Rev E. 2016 May;93(5):052211. doi: 10.1103/PhysRevE.93.052211. Epub 2016 May 13.
6
Gibbs states and the set of solutions of random constraint satisfaction problems.吉布斯态与随机约束满足问题的解集
Proc Natl Acad Sci U S A. 2007 Jun 19;104(25):10318-23. doi: 10.1073/pnas.0703685104. Epub 2007 Jun 13.
7
Phase transitions in the coloring of random graphs.随机图着色中的相变。
Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Sep;76(3 Pt 1):031131. doi: 10.1103/PhysRevE.76.031131. Epub 2007 Sep 26.
8
Exact satisfiability threshold for k-satisfiability problems on a Bethe lattice.贝叶斯晶格上k - 可满足性问题的精确可满足性阈值。
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Oct;92(4):042144. doi: 10.1103/PhysRevE.92.042144. Epub 2015 Oct 21.
9
Simplifying random satisfiability problems by removing frustrating interactions.
Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Oct;74(4 Pt 1):041105. doi: 10.1103/PhysRevE.74.041105. Epub 2006 Oct 6.
10
Clustering of solutions in the random satisfiability problem.随机可满足性问题中解的聚类
Phys Rev Lett. 2005 May 20;94(19):197205. doi: 10.1103/PhysRevLett.94.197205. Epub 2005 May 19.

引用本文的文献

1
Complete realization of energy landscapes and non-equilibrium trapping dynamics in small spin glass and optimization problems.小自旋玻璃中能量景观和非平衡俘获动力学的完全实现及优化问题。
Sci Rep. 2024 Jul 8;14(1):15675. doi: 10.1038/s41598-024-65493-4.
2
Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming.用线性规划研究随机可满足性问题的典型算法复杂度的相变。
PLoS One. 2019 Apr 19;14(4):e0215309. doi: 10.1371/journal.pone.0215309. eCollection 2019.
3
The backtracking survey propagation algorithm for solving random K-SAT problems.
回溯式调查传播算法求解随机 K-SAT 问题。
Nat Commun. 2016 Oct 3;7:12996. doi: 10.1038/ncomms12996.