偏極ランダムk-SAT【JST・京大機械翻訳】

Danielsson Joel Larsson; Markstrom Klas

プレプリント

J-GLOBAL ID：202202208023084508 整理番号：22P0331903

偏極ランダムk-SAT【JST・京大機械翻訳】

Polarised random k-SAT

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年04月13日プレプリントサーバーでの情報更新日： 2023年01月12日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,偏光ランダムk-SATと呼ばれるランダムk-SAT問題の変化を研究した。このモデルでは,偏光パラメータpがあり,各変数が確率pと純粋に負えられるが,他の半分では確率は交換される。p=1/2に対して,古典的ランダムk-SATモデルを得て,他の極値において,p=0または1の完全に分極したモデルを得た。ここでは,すべてのk変数が純粋に生じ,すべてのk変数がネギュレーションが起こるクラスユースの2つのタイプのみが存在する。すなわち,p=0の場合,ランダム単調k-SATの事例を得た。充足可能性の閾値は,pが1/2から離れるにつれて減少せず,従って,偏光ランダムk-SATに対する充足可能性閾値は,ランダムk-SATの閾値上の上限であることを示した。実際,漸近的に2つの閾値が一致すると推測した。【JST・京大機械翻訳】

,
, 【Automatic Indexing@JST】

人工知能 , 計算理論 , 論理代数

前のページに戻る