论文纲要：对于牵制满意题目透彻相变的几何接洽

牵制满意题目 (Constraint Satisfaction Problem，简称为 CSP) 由一组变量和一组牵制前提构成.对这组变量的赋值称为该 CSP 的解, 即使满意一切的牵制前提.人为智能和计划机科学等稠密范围中的很多题目最后都归纳为 CSP, 这使得对 CSP 的接洽有着要害的表面与实际意旨.相变局面普遍生存于 CSP 中, 它反应了题目的内涵实质.相变局面是一种渐变局面: 当随机 CSP 模子的牵制前提由弱至强普遍地平均变革时, 随机 CSP 模子天生的随机 CSP 范例由首先以几率 1 有解，在过程某一临界点后变为以几率 1 无解并维持到结果.这种渐变局面也普遍生存于天然界中, 比方物资的三态变化.全文共分六章. 第一章大略引见了正文的接洽处事. 第二章扼要引见了 CSP 的基础观念及分门别类, 接洽相变局面的基础数学本领及常用数学软硬件东西, 并在渐近级数与 Taylor 级数之间创造了接洽, 给出了求 Stirling 级数, Gosper 公式以及 Ramanujan 公式的领会本领, 并实行了 Gosper 公式及 Ramanujan 公式.在第三章中, 咱们接洽了第一类随机 $k$-SAT 模子.用 $F_{k}(n, rn)$ 表白 $n$ 个布尔变量 $r n$ 个子句的 $k$-CNF 公式.设 $kgeq 2$ 是大肆给定的正平头, 与布尔变量的个数 $n$ 无干. 设置egin{align}onumberr_{k}=supleft{r: lim_{nightarrowinfty} ext{f P}left[F_{k}(n, rn) ext{可满意}ight]=1ight}.end{align}咱们提出了一种新的加权本领:任给赋值 $sigmain {0, 1}^{n}$ 和子句 $c=ell_{1}veecdotsveeell_{k}$.设置 $d=d(sigma, c)$ 为在赋值 $sigma$ 下子句 $c$ 的 $k$ 个笔墨 $ell_{1}, cdots, ell_{k}$ 中被满意的笔墨的个数.对大肆给定的 $eta>-1$ 和 $lambda>0$, 设置egin{align}onumberomega(sigma, c)proptoleft{ egin{array}{cl} 0 & d=0, lambda(1+eta) & d=1, lambda^{d} & ext{其余}. end{array} ight.end{align}运用该加权本领, 咱们获得了 $r_{3}geq 2.83$, $r_{4}geq 8.09$, $r_{5}geq 18.91$, $r_{6}geq 40.81$, $r_{7}geq 84.87$,矫正了 D. Achlioptas 和 Y. Peres 在 2003 年提出的加权本领的截止 $r_{3}geq 2.68$, $r_{4}geq 7.91$, $r_{5}geq 18.79$, $r_{6}geq 40.74$, $r_{7}geq 84.82$.Achlioptas 和 Peres 的加权本领是egin{align}onumberomega(sigma, c)proptoleft{ egin{array}{cl} 0 & d=0, lambda^{d} & ext{其余}. end{array} ight.end{align}据咱们所知, 个中 $r_{5}geq 18.91$, $r_{6}geq 40.81$, $r_{7}geq 84.87$ 是暂时最佳的下界.在第四章中, 咱们接洽了第二类随机 $k$-SAT 模子.用 $F_{k}(n, m)$ 表白 $n$ 个布尔变量 $m$ 个子句的 $k$-CNF 公式.大肆给定 $epsilon>0$.若 $kgeq left(frac{1}{2}+epsilonight)log_{2} n$, 则随机 $k$-SAT 模子在 $m=nleft(2^{k}+O(1)ight)ln 2$ 邻近生存透彻相变局面.这一论断矫正了 A. Frieze 和 N.C. Wormald 在 2005 年获得的前提 $k-log_{2}nightarrow +infty$.在第六章中, 咱们接洽了 $(k, q)$-SAT 模子.$(k, q)$-SAT 模子是对随机 $k$-SAT 模子或随机 NAE $k$-SAT 模子的实行.用 $F_{k}(n, m)$ 表白 $n$ 个布尔变量 $m$ 个子句的 $k$-CNF 公式.给定非空汇合 $QsubseteqBig{0, 1Big}^{k}$, 个中 $|Q|=q$.任给赋值 $sigmainBig{0, 1Big}^{n}$.若赋值 $sigma$ 使得 $F_{k}(n, m)$ 的 $m$ 个子句的取值都不落在汇合 $Q$ 中, 则称赋值 $sigma$ 是一个解.当 $Q=left{0^{k}ight}$ 时, $(k, q)$-SAT 即是随机 $k$-SAT; 当 $Q=left{0^{k}, 1^{k}ight}$ 时, $(k, q)$-SAT 即是随机 NAE $k$-SAT.商量如许天生的 $k$-CNF 公式 $F_{k}(n, p)$:egin{itemize}item 设 $V=Big{x_{1}, cdots, x_{n}Big}$ 是 $n$ 个布尔变量的汇合. $C_{k}(V)$ 是由 $V$ 中的 $n$ 个布尔变量天生的一切的 $2^{k}n^{k}$ 个 $k-hspace{-0.5mm} ext{子句}$ 构成的汇合.item 独登时以几率 $p=p(n)$ 包括 $C_{k}(V)$ 中的每一个 $k-hspace{-0.5mm} ext{子句}$.end{itemize}设 $qgeq 1$ 是给定的正平头, 与布尔变量的个数 $n$ 无干.大肆给定 $ heta>0$.若 $kgeq left(1+ hetaight)log_{2} n$, 则 $(k, q)$-SAT 模子生存透彻相变局面.这一截止矫正了 A.D. Flaxman 在 2004 年获得的前提 $kgeq D_{epsilon, q}log_{2} n$ ($epsilon$ 是刻划临界区间长度的参数, $epsilon$ 越小则临界区间长度越短), 个中当 $epsilonightarrow 0$ 或 $qightarrowinfty$ 时 $D_{epsilon, q}ightarrowinfty$.在第六章中, 咱们接洽了RB模子.RB模子有可证的透彻相变点和简单爆发难解范例的特性, 这使得它变成定义域可变的这一类随机 CSP 模子中最要害的模子之一.设 RB 模子的牵制效率域 (Constraint Scopes) 长度为 $k$, 定义域巨细为 $d=n^{alpha}$ 和不相容赋值范围为 $p imes d^{k}$.若 $(2k-1)alpha>1$, $k geq frac{ auln au}{ au -1}$ (个中 $ au =frac{1}{1-p}$ 或 $ au=e^{alpha/r}$), 则 RB 模子生存透彻相变点.这一论断矫正了承诺和李未在 2000 年获得的前提 $kalpha>1$, $k geq au$.