题目：关于约束满足问题精确相变的若干研究

约束满足问题 (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}

onumber
r_{k}=supleft{r: lim_{n ightarrowinfty} ext{f P}left[F_{k}(n, rn) ext{可满足} ight]=1 ight}.
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}

onumber
omega(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}

onumber
omega(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}+epsilon ight)log_{2} n$, 则随机 $k$-SAT 模型在 $m=nleft(2^{k}+O(1) ight)ln 2$ 附近存在精确相变现象.
这一结论改进了 A. Frieze 和 N.C. Wormald 在 2005 年得到的条件 $k-log_{2}n ightarrow +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+ heta ight)log_{2} n$, 则 $(k, q)$-SAT 模型存在精确相变现象.
这一结果改进了 A.D. Flaxman 在 2004 年得到的条件 $kgeq D_{epsilon, q}log_{2} n$ ($epsilon$ 是刻画临界区间长度的参数, $epsilon$ 越小则临界区间长度越短), 其中当 $epsilon ightarrow 0$ 或 $q ightarrowinfty$ 时 $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$.