文献

J-GLOBAL ID：202202242505688668   整理番号：22A1077276

3SAT問題に対するバイアスPPSZアルゴリズムの改善

An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem

著者 (2件)： QIN Tong (SIT Division, Makino Milling Machine Co., Ltd.) ,  WATANABE Osamu (School of Computing, Tokyo Institute of Technology)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E105.D  号： 3  ページ： 481-490(J-STAGE)  発行年： 2022年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Hansen,Kaplan,ZamirおよびZwick(STOC 2019)は,PPSZ過程におけるBoole変数への割り当てを予測するための「バイアス」を使用した系統的方法を導入し,彼らのバイアスPPSZアルゴリズムが,一意的3SATに対してPPSZの比較的大きな成功確率改善を達成することを示した。著者らは,「バイアス」を使用する追加的な方法を提案し,さらに改良されることを数値解析によって示した。(翻訳著者抄録)

シソーラス用語： *充足可能性問題 ,  *Boole代数 ,  バイアス ,  計算理論

著者キーワード (5件)： 3SAT ,  ランダム化アルゴリズム ,  PPSZ ,  バイアス付きPPSZ ,  数値解析

分類 (1件)： 数値計算  (JE02000J)

引用文献 (10件)：

• [1] S. Baumer and R. Schuler, “Improving a probabilistic 3-SAT algorithm by dynamic search and independent clause pairs,” Proc. 6th Int'l Conference on Theory and Applications of Satisfiability Testing, LNCS, vol.2919, pp.150-161, 2003. 10.1007/978-3-540-24605-3_12
• [2] T.D. Hansen, H. Kaplan, O. Zamir, and U. Zwick, “Faster k-SAT algorithms using biased-PPSZ,” Proc. 51st Annual ACM Sympos. on Theory of Computing, ACM Press, pp.578-589, 2019. 10.1145/3313276.3316359
• [3] T. Hertli, “Breaking the PPSZ barrier for Unique 3-SAT,” Proc. Int'l Colloquium on Automata, Languages, and Programming, LNCS, vol.8572, pp.600-611, 2014. 10.1007/978-3-662-43948-7_50
• [4] T. Hertli, “3-SAT faster and simpler - Unique-SAT bounds for PPSZ hold in general,” SIAM J. Comput., vol.43, no.2, pp.718-729, 2014. 10.1137/120868177
• [5] T. Hofmeister, U. Schoning, R. Schuler, and O. Watanabe, “Randomized algorithms for 3-SAT,” Theory of Computing Systems, vol.40, pp.249-262, 2007. 10.1007/s00224-005-1275-6

タイトルに関連する用語 (2件)： バイアス ,  アルゴリズム