Art

J-GLOBAL ID：201702265691955316   Reference number：17A1696503

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

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

Author (2)： QIN Tong (Tokyo Inst. of Technol., Tokyo, JPN) ,  WATANABE Osamu (Tokyo Inst. of Technol., Tokyo, JPN)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 117  Issue： 269(COMP2017 20-25)  Page： 5-12  Publication year： Oct. 20, 2017 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *fast algorithm ,  speedup ,  computational complexity ,  unity ,  Boolean function ,  NP complete problem ,  *satisfiability problem ,  propositional logic ,  exponential function ,  *computational complexity theory
Semi thesaurus term： computational complexity ,  randomized algorithm ,  polynomial time algorithm

JST classification (1)： Theory of computation  (JB02000A)

Reference (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.

Terms in the title (2)： 解 ,  アルゴリズム