本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #111
- 日期：2026-03-18
摘要
精確覆蓋的 k 均勻、d 正規實例是 m 個集合 F n,d,k = { S j ⊆ {1, . 。 。 , n }}，其中每個子集的大小為 k，且每個 1 ≤ i ≤ n 都包含在 S j 的 d 中。若存在子集 T ⊆ {1,…, n } 使得 | 是可滿足的T ∩ S j | = 1 對所有 j 。或者，我們可以將其視為 Positive 1-in-k SAT 的 d 正規實例，即具有 m 個子句和 n 個變數的布林公式，其中每個子句包含 k 個變數並要求其中一個恰好為真。我們用 k > 2 來確定這種類型的隨機實例的可滿足性閾值。讓我們證明，如果 d < d ⋆ ，則 F n,d,k 高機率可滿足；如果 d > d ⋆ ，則 F n,d,k 高機率不可滿足。我們透過簡單應用一階矩和二階矩方法來實現這一點，使用小子圖調節方法將滿足性機率提高到 d ⋆ 以下至 1 − o (1)。