本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
EXACTCOVER 的 k-均勻、d-正則實例是 m 個集合 F-n,F- d,F- k = {S-j 1 {1, ..., n}} 的子集，其中每個子集的大小為 k，並且每個 1 <= i <= n 都包含在 (S)j 的 d 中。若存在 {1, ..., n} 的子集 T 子集，使得對所有 j，垂直條 T 布林值 AND S-j 垂直條 = 1，則可滿足。或者，我們可以將其視為 POSITIVE 1-IN-K SAT 的 d-正規實例，即。即，具有 m 個子句和 n 個變數的布林公式，其中每個子句包含 k 個變數並要求其中一個恰好為真。我們確定 k > 2 的此類隨機實例的可滿足性閾值。令 d(star) = ln k/(k - 1)(-ln(1 - 1/k)) + 1，我們表明，如果 d < d(star)，則 F-n,F- d,F- k 高機率可滿足，如果 d > d(star)，則高機率不可滿足。我們透過簡單應用一階矩和二階矩方法來實現此目的，使用小子圖調節方法將 d(star) 以下的可滿足性機率提高到 1 - o(1)。