Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-010 | 13th February 2003 00:00

Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

RSS-Feed




TR03-010
Authors: Sven Baumer, Rainer Schuler
Publication: 17th February 2003 16:24
Downloads: 3437
Keywords: 


Abstract:

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)
is a well known NP-complete problem and the development of faster
(moderately exponential time) algorithms has received much interest
in recent years. We show that the 3-SAT problem can be solved by a
probabilistic algorithm in expected time O(1,3290^n).
Our approach is based on Schoening's random walk algorithm for
k-SAT, modified in two ways.



ISSN 1433-8092 | Imprint