论文标题
偏振随机K-SAT
Polarised random k-SAT
论文作者
论文摘要
在本文中，我们研究了随机$ k $ -sat问题的变体，称为偏振随机$ k $ -sat。在此模型中，有一个极化参数$ p $，在一半的子句中，每个变量都与概率$ p $和纯净的否定为否则，而另一半则互换。对于$ p = 1/2 $，我们获得了经典的随机$ k $ -sat型号，在另一个极端情况下，我们具有完全极化的模型，其中$ p = 0 $或$ 1 $。这里只有两种类型的条款：所有$ k $变量纯粹出现的条款，以及所有$ k $变量否定为否定的条款。也就是说，对于$ p = 0 $，我们得到一个随机单调$ k $ -sat的实例。我们表明，满意度的阈值不会降低，因为$ p $从$ \ frac {1} {2} $移动，因此，偏光随机$ k $ -sat的满足性阈值是随机$ k $ -sat的阈值的上限。实际上，我们猜想这两个阈值一致。
In this paper we study a variation of the random $k$-SAT problem, called polarized random $k$-SAT. In this model there is a polarization parameter $p$, and in half of the clauses each variable occurs negated with probability $p$ and pure otherwise, while in the other half the probabilities are interchanged. For $p=1/2$ we get the classical random $k$-SAT model, and at the other extreme we have the fully polarized model where $p=0$, or $1$. Here there are only two types of clauses: clauses where all $k$ variables occur pure, and clauses where all $k$ variables occur negated. That is, for $p=0$ we get an instance of random monotone $k$-SAT. We show that the threshold of satisfiability does not decrease as $p$ moves away from $\frac{1}{2}$ and thus that the satisfiability threshold for polarized random $k$-SAT is an upper bound on the threshold for random $k$-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
