Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > 3SAT:
Reports tagged with 3SAT:
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 >>>


TR04-016 | 3rd March 2004
Michael Alekhnovich, Eli Ben-Sasson

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

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


TR04-111 | 30th November 2004
Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

Computational Complexity of Some Restricted Instances of 3SAT

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

more >>>

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

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


TR17-140 | 11th September 2017
Tong Qin, Osamu Watanabe

An improvement of the algorithm of Hertli for the unique 3SAT problem

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

more >>>

TR24-104 | 12th June 2024
Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>




ISSN 1433-8092 | Imprint