- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
A Probabilistic 3—SAT Algorithm Further Improved
Description
In [Sch99], 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.3334n) when given a formula F on n variables. This was the up to now best running time known for an algorithm solving 3-SAT. Here, we describe an algorithm which improves upon this time bound by combining an improved version of the above randomized algorithm with other randomized algorithms. Our new expected time bound for 3-SAT is O(1.3302n).
