|
|||||
|
|
Derandomizing the HSSW Algorithm for 3-SAT |
|
| Authors: | Kazuhisa Makino Suguru Tamaki Masaki Yamamoto |
| Affiliation: | 1. Graduate School of Information Science and Technology, University of Tokyo, Tokyo, Japan 2. Graduate School of Informatics, Kyoto University, Kyoto, Japan 3. Department of Computer and Information Science, Seikei University, Tokyo, Japan |
| Abstract: | We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schöning, Schuler, and Watanabe (in STACS 2002, pp. 192–202, 2002). Thereby, we obtain an O(1.3303 n )-time deterministic algorithm for 3-SAT, which is currently fastest. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |
