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
$O(c^n)$. Roughly speaking most algorithms are based on
Davis-Putnam. \cite{Sch99} is the first local search algorithm which
gives a guaranteed performance for general instances and
\cite{DGH+02}, \cite{HSSW02} and \cite{BS03} follow up this
Sch\"oning's approach.

3-SAT | 4-SAT | 5-SAT | 6-SAT | type | ref.
-------------------------------------------------
1.782 | 1.835 | 1.867 | 1.888 | det. | [PPZ97]
1.618 | 1.839 | 1.928 | 1.966 | det. | [MS85]
1.588 | 1.682 | 1.742 | 1.782 | prob. | [PPZ97]
1.579 | - | - | - | det. | [Sch92]
1.505 | - | - | - | det. | [Kul99]
1.481 | 1.6 | 1.667 | 1.75 | det. | [DGH+02]
1.362 | 1.476 | 1.569 | 1.637 | prob. | [PPSZ98]
1.334 | 1.5 | 1.6 | 1.667 | prob. | [Sch99]
1.3302 | - | - | - | prob. | [HSSW02]
1.3290 | - | - | - | prob. | [BS03]
1.324 | 1.474 | - | - | prob. | [*]

Our new bounds are denoted by [*] in the above list, namely we prove
that for any satisfiable $n$-variable 3-CNF \ (4-CNF) formula
$F$, there exists a randomized algorithm that finds a satisfying
assignment of $F$ in expected running time $O(1.324^n)$
($O(1.474^n)$). The basic idea is to combine two existing algorithms,
the one by Paturi, Pudl\'ak, Saks and Zane \cite{PPSZ98} and the other
by Sch\"oning \cite{Sch99}. It should be noted, however, that simply
running the two algorithms independently does not seem to work. Also,
our approach can escape one of the most complicated portions in the
analysis of \cite{PPSZ98}. In this paper we focus on the 3-SAT case;
the 4-SAT case is very similar and may be omitted. The same approach
does not improve the bounds for 5-SAT or more.