文献

J-GLOBAL ID：202002285004937796   整理番号：20A2077971

局所レマ領域におけるk-SAT解の高速サンプリングと計数【JST・京大機械翻訳】

Fast sampling and counting k-SAT solutions in the local lemma regime

著者 (4件)： Feng Weiming (Nanjing University, China) ,  Guo Heng (University of Edinburgh, UK) ,  Yin Yitong (Nanjing University, China) ,  Zhang Chihao (Shanghai Jiao Tong University, China)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2020  ページ： 854-867  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 各変数が大部分のd時間で現れるk-均一CNF公式への割り当てを満たすため,Markov連鎖に基づく新しいアルゴリズムを与えた。kd<no(1)とk≧20logk+20logd+60の任意のkとdに対して,新しいサンプリングアルゴリズムは線形時間で実行され,計数アルゴリズムは二次時間に近い。著者らのアプローチは,近似計数においてLovaz局所補助定理を著しく利用するMoitra(JACM,2019)によって触発された。著者らの主な技術的貢献は,従来のMarkov連鎖アプローチにおける連結性障壁を迂回するために局所補助定理を使用することであり,それはSAT解のような非連結状態空間に適用できるよく開発されたMCMC法を作る。著者らのアプローチの利点は,k=ω(1)またはd=ω(1)であっても,局所構造の計数を避け,固定多項式実行時間を得ることである。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  多項式 ,  *Markov連鎖 ,  近似法 ,  線形性 ,  連結性
準シソーラス用語： 局所構造 ,  MCMC ,  実行時間 ,  状態空間 ,  補題 , 【Automatic Indexing@JST】

著者キーワード (4件)： k-SAT ,  Lov’asz局所補題 ,  Markov連鎖モンテカルロ法 ,  近似計数

分類 (4件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  数値計算  (JE02000J) ,  物理化学一般  (CB01010X)

タイトルに関連する用語 (4件)： SAT ,  解 ,  サンプリング ,  計数