報 每日報告新聞網
聖塔非研究所

隨機滿足性的選擇力量

2026-03-18 · 工作論文 · 更新 2026/03/18 下午01:16

摘要 我們考慮 k SAT 公式的 Achlioptas 過程。我們建立一個包含 n 個變數和 m 個子句的半隨機公式，其中每個子句都是兩個或多個均勻隨機子句之間在線上做出的選擇。我們的目標是延遲可滿足性/不可滿​​足性轉換，使公式在超出隨機 k SAT 的可滿足性閾值 alpha k 的密度 m/n 下可滿足。我們表明，三個選擇足以提高任何 k = 3 的閾值，並且兩個選擇足…

原文連結PDF 來源

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

論文資訊

  • 類型：工作論文
  • 編號：工作論文 #187
  • 日期：2026-03-18

摘要

我們考慮 k-SAT 公式的 Achlioptas 過程。我們建立一個包含 n 個變數和 m 個子句的半隨機公式，其中每個子句都是兩個或多個均勻隨機子句之間在線上做出的選擇。我們的目標是延遲可滿足性/不可滿​​足性轉換，使公式在超出隨機 k-SAT 的可滿足性閾值 alpha_k 的密度 m/n 下可滿足。我們表明，三個選擇足以提高任何 k >= 3 的閾值，並且兩個選擇足以滿足所有 3 <= k <= 25。我們還表明，兩個選擇足以降低所有 k >= 3 的閾值，使得公式在低於 alpha_k 的密度下不可滿足。