SAT問題における分布に基づくサンプリングと重み付けモデルカウント

• CNF式に対する重み付けモデルカウントは重要な問題です。
• 新たなパラメータ「tilt」を用いて効率的な手法を提案します。
• 理論的保証が強く、数千の変数にスケール可能です。

CNF式に対する重み付けモデルカウントとサンプリングは、さまざまな応用がある重要な問題です。本論文では、新しいパラメータ「tilt」を導入し、ブラックボックスオラクルを用いた効率的な解法を提案します。このアプローチは理論的な保証が強く、数千の変数を扱う問題にも対応可能です。特に、計算効率を改善する新しい手法を探している研究者や実務者に向いています。

計算理論やSAT問題に興味がある研究者やエンジニアに最適です。