Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with 3-SAT:
TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

3-Coloring in time O(1.3446^n): a no-MIS algorithm

We consider worst case time bounds for NP-complete problems
including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.
Our algorithms are based on a common generalization of these problems,
called symbol-system satisfiability or, briefly, SSS [R. Floyd &
R. Beigel, The Language of Machines]. 3-SAT is equivalent to
(2,3)-SSS while the other problems ... more >>>

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-054 | 2nd July 2003
Daniel Rolf

3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses

This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share ... more >>>

TR05-159 | 14th November 2005
Daniel Rolf

Improved Bound for the PPSZ/Schöning-Algorithm for $3$-SAT

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>>

ISSN 1433-8092 | Imprint