論文の概要: Targeting Clause Type Distributions: a Picklock for Random Satisfiability Problems

• arxiv url: http://arxiv.org/abs/2605.20328v1
• Date: Tue, 19 May 2026 18:00:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.298232
• Title: Targeting Clause Type Distributions: a Picklock for Random Satisfiability Problems
• Title（参考訳）: クロース型分布のターゲット:ランダム満足度問題に対するピックロック
• Authors: J. Schwardt, J. C. Budich,
• Abstract要約: 本稿では,最も難しい3つのSAT問題を解くために,Target-SAT (TSAT)アルゴリズムを提案する。 TSATは、その検索において、関連するローカル検索空間内のターゲットに向けて活発にガイドされている。 また, 局所探索アルゴリズムが比較的小さなシステムに制限されている理由を, 膨大な低エネルギートラップにより解析した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization problems such as the NP-complete 3-SAT provide an important benchmark for the difficult task of finding ground-states in strongly correlated many-body systems with rugged energy landscapes. The study of random 3-SAT problems as Ising spin Hamiltonians in statistical physics has yielded major insights including the existence of a satisfiability phase transition, and the prediction of a critical parameter line of particularly hard instances. Yet, progress on solving those instances has been scarce for several decades. Here, introducing the Target-SAT (TSAT) algorithm, we roughly triple the tractable problem sizes in the hardest regime, with an even greater improvement in a vast range of neighboring regions. By leveraging statistical information hidden in the combinatorial constraints of the problem, TSAT is actively guided in its stochastic local search toward a target within the relevant parameter space. Our analysis also explains why established local search algorithms are limited to relatively small system sizes due to a vast low-energy trap. Furthermore, we characterize the aforementioned critical line in terms of a dominant additional complexity barrier, whose exponential scaling is quickly overcome by TSAT only in the surrounding parameter space. With TSAT, the lead in solving the hardest known random satisfiability problems returns to the realm of stochastic local search algorithms.
• Abstract（参考訳）: NP完全3SATのような最適化問題は、強相関多体系における強相関の強いエネルギー景観の基底状態を見つけることの難しい課題に対する重要なベンチマークとなる。 統計物理学におけるイジング・スピン・ハミルトニアン(Ising spin Hamiltonians)のようなランダムな3SAT問題の研究は、満足度相転移の存在や、特にハードなインスタンスの臨界パラメータ線の予測など、大きな洞察をもたらした。 しかし、これらのインスタンスの解決の進歩は数十年間ほとんど行われていない。 ここでは、TSATアルゴリズムを導入し、最も厳しい状況下でのトラクタブルな問題のサイズを約3倍にし、近隣の広範囲でさらに改善した。 問題の組合せ制約に隠れた統計情報を活用することにより、TSATはその確率的局所探索において、関連するパラメータ空間内の対象に向かって積極的に誘導される。 また, 局所探索アルゴリズムが比較的小さなシステムに制限されている理由を, 膨大な低エネルギートラップにより解析した。 さらに, 上記の臨界線を, 周辺パラメータ空間のみにおいて, 指数的スケーリングがTSATによって急速に克服されるような, 優位な付加的複雑性障壁の観点から特徴づける。 TSATでは、最も難しいランダムな満足度問題の解法は確率的局所探索アルゴリズムの領域に戻る。

関連論文リスト

• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。 我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。 従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
  論文  参考訳（メタデータ） (2025-12-04T14:11:52Z)
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints [0.0]
  NP完全満足度問題 3-SAT の局所探索を導入,ベンチマークする。 私たちの建設は、WalkSATのような確立した従来のアプローチが、地元のミニマで立ち往生する傾向にあるという決定的な観察に基づいています。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。
  論文  参考訳（メタデータ） (2025-06-18T18:00:01Z)
• Noise to the Rescue: Escaping Local Minima in Neurosymbolic Local Search [50.24983453990065]
  結合と解離を min と max で表す Godel 論理に BP を適用することは SAT 問題解決のための局所探索アルゴリズムと等価であることを示す。 本稿では,モデルのロジットに雑音を付加し,局所最適化から逃れるゴデルトリックを提案する。
  論文  参考訳（メタデータ） (2025-03-03T18:42:13Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-09-20T16:27:52Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。 提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。 大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
  論文  参考訳（メタデータ） (2022-11-02T14:35:13Z)
• Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization [1.1783108699768]
  適応的勾配自由戦略を開発することにより,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入する。 我々は、特殊解法と汎用解法の両方に対して、大幅な高速化と堅牢性を観察する。
  論文  参考訳（メタデータ） (2021-11-26T17:45:32Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。