Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > K-SAT:
Reports tagged with k-SAT:
TR05-027 | 19th February 2005
Daniel Rolf

Derandomization of PPSZ for Unique-$k$-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 formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... 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 >>>


TR06-062 | 24th April 2006
Subhas Kumar Ghosh

Unique k-SAT is as Hard as k-SAT

Revisions: 1 , Comments: 3

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>


TR10-095 | 11th June 2010
Masaki Yamamoto

A combinatorial analysis for the critical clause tree

In [FOCS1998],
Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm
for finding a satisfying assignment of a $k$-CNF formula.
The main lemma of the paper is as follows:
Given a satisfiable $k$-CNF formula that
has a $d$-isolated satisfying assignment $z$,
the randomized algorithm finds $z$
with probability at ... more >>>




ISSN 1433-8092 | Imprint