文献

J-GLOBAL ID：201702265691955316   整理番号：17A1696503

単一解3SAT問題に対するHertliアルゴリズムの改良

An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem

著者 (2件)： QIN Tong (Tokyo Inst. of Technol., Tokyo, JPN) ,  WATANABE Osamu (Tokyo Inst. of Technol., Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 269(COMP2017 20-25)  ページ： 5-12  発行年： 2017年10月20日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 単一解3SAT問題を著名なPPSZアルゴリズムより高速で解くHertliのアルゴリズムに対し,単純であるが非自明な改善を与える方法を提案する。アルゴリズム自体は単一解3SAT問題に対するものだが,最近の結果を用いると,一般の3SAT問題に対しても既存のものより高速なアルゴリズムを得ることができる。高速化の度合いは極わずかだが,この考え方がより大きな改良へとつながることを期待している。(著者抄録)

シソーラス用語： *高速アルゴリズム ,  高速化 ,  計算量 ,  単一性 ,  Boole関数 ,  NP完全問題 ,  *充足可能性問題 ,  命題論理 ,  指数関数 ,  *計算量理論
準シソーラス用語： 計算複雑性 ,  ランダマイズドアルゴリズム ,  多項式時間アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

引用文献 (8件)：

• T. Hertli, 3-SAT faster and simpler.unique-SAT bounds for PPSZ hold in general, FOCS'11, 277-284, 2011.
• T. Hertli, Breaking the PPSZ barrier for unique 3-SAT, ICALP'14, LNCS 8572, 8-11, 2014.
• T. Hertli, Improved Exponential Algorithms for SAT and ClSP, A thesis for Doctor of Sciences of ETH Zurich, 2015.
• R. Paturi, P. Pudlak, M.E. Saks, and F. Zane, An improved exponential-time algorithm for k-SAT, J. ACM, 52(3):337-364, 2005.
• R. Paturi, P. Pudlak, and F. Zane, Satisfiability coding lemma, Chicago J. Theoret. Comput. Sci., 11-19, 1999.

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