论文摘要：随机K-SAT相变点邻近的一种典范构造

随机K-SAT题目是表面计划机科学的一个要害接洽范围. 伴跟着随机K-SAT的可满意性相变，爆发了一种大略探求算法的计划本钱上的相变. 这种简直同步的相变出此刻第一次全国代表大会类的NPC题目中，这种偶然激励了接洽职员对于NPC题目的构造，衍化以及其对计划模子的符合性的探究.正文第一局部截止计划在随机K-SAT的可满意相变题目中, 其解空间跟着序参数衍化的进程；提出了相变点邻近的一种新的典范构造---长程等价类；并把这种等价类的思维运用到扰动图中, 指出等价的自旋极点在扰动图中将会产生环状构造, 由此证明了接洽职员对于扰动图中的圈的持久探求：扰动图中的大标准的圈的展示, 是致展示计划上的相变的一个大概的要害因为. 进一步, 正文对大标准限制交互效率的粒子体例的普遍性相变表面举行了计划, 获得了更为普遍的Gibbs猜想独一性的辨别规则. 在 Weitz 和Winkler的处事的普通上, 咱们运用路途啮合的本领, 把Dobrushin的点对点（经过点建立）的感化实行到块对块（经过块建立）的情势. 在此提出的独一性前提和空间关系蜕化的观念是精细接洽的,而且咱们设置的感化的襟怀包括了之前Dobrishin和Weitz设置的襟怀. 　　正文共分四章．第一章引见了随机K-SAT题目及其同步相变局面, 计划相变点邻近大略探求算法的计划本钱遽然减少的大概因为.第二章是第三章的表面普通，引见了平稳态统计物理本领在拉拢优化题目领会中的运用.第三章是咱们的第一局部截止, 咱们用Cavity Method 在 RS 档次上对建立在随机图上的极小极点掩盖题目和随机K-SAT题目中的等价类的分别举行了接洽, 计划了该类体例在相变点邻近的解空间展示的一种新的典范构造，即长程等价类．第四章是咱们的第二局部截止，重要对大标准限制交互效率的粒子体例的普遍性相变表面举行了计划, 获得了更为普遍的有限/无穷图上的Gibbs猜想独一性的辨别规则.