Daniel Rolf

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 >>>

Michael Alekhnovich, Eli Ben-Sasson

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time

of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The class QMA(k), introduced by Kobayashi et al., consists

of all languages that can be verified using k unentangled quantum

proofs. Many of the simplest questions about this class have remained

embarrassingly open: for example, can we give any evidence that k

quantum proofs are more powerful than one? Can ...
more >>>

Tong Qin, Osamu Watanabe

We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem.

more >>>