Randomized Algorithms for 3-SAT |
| |
| Authors: | Thomas Hofmeister Uwe Schoning Rainer Schuler Osamu Watanabe |
| |
| Affiliation: | (1) Informatik 2, Universitat Dortmund, 44221 Dortmund, Germany;(2) Abteilung fur Theoretische Informatik, Universitat Ulm, Oberer Eselsberg, 89069 Ulm, Germany;(3) Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, W8-25, Tokyo 152-8552, Japan |
| |
| Abstract: | Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm
has an expected running time of poly(n)·(4/3)n = O(1.334n). In this paper we present randomized algorithms
and show that one of them has O(1.3302n) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT
is the one given by Iwama and Tamaki that runs in O(1.324n).) |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
