Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probabilistic algorithm:
TR03-010 | 13th February 2003
Sven Baumer, Rainer Schuler

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

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).
more >>>

TR03-053 | 8th July 2003
Kazuo Iwama, Suguru Tamaki

Improved Upper Bounds for 3-SAT

This paper presents a new upper bound for the
$k$-satisfiability problem. For small $k$'s, especially for $k=3$,
there have been a lot of algorithms which run significantly faster
than the trivial $2^n$ bound. The following list summarizes those
algorithms where a constant $c$ means that the algorithm runs in time
more >>>

ISSN 1433-8092 | Imprint