论文标题
稀疏随机关系结构上的一阶句子的概率：在随机CNF公式上的确定性应用
Probabilities of first order sentences on sparse random relational structures: An application to definability on random CNF formulas
论文作者
论文摘要
我们将Lynch证明的稀疏随机图扩展到任意关系语言。我们考虑一个有限的关系词汇$σ$和一阶理论$ t $，$σ$由对称性和反射性公理组成。我们定义了满足$ t $的有限$σ$结构的二项式随机模型，并表明一阶属性具有明确定义的渐近概率，而当预期满足$σ$的每个关系的元素是线性的。还表明，相对于代表词汇$σ$中每个关系$ r $的几个参数，这些限制概率就表现得很好。提出了这些结果将这些结果应用于随机布尔可满足性问题。我们表明，在$ n $变量上的随机$ k $ -cnf公式中，每个可能的子句都以概率$ \ sim c/n^{k-1} $发生，独立于任何一阶属性属性$ k $ -cnf公式，暗示不可满足性几乎不能肯定地持有，因为$ n $倾向于$ n $。
We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary $σ$ and a first order theory $T$ for $σ$ composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite $σ$-structures that satisfy $T$ and show that first order properties have well defined asymptotic probabilities when the expected number of tuples satisfying each relation in $σ$ is linear. It is also shown that these limit probabilities are well-behaved with respect to several parameters that represent the density of tuples in each relation $R$ in the vocabulary $σ$. An application of these results to the problem of random Boolean satisfiability is presented. We show that in a random $k$-CNF formula on $n$ variables, where each possible clause occurs with probability $\sim c/n^{k-1}$, independently any first order property of $k$-CNF formulas that implies unsatisfiability does almost surely not hold as $n$ tends to infinity.
