solving #SAT in poly(number of vars) and exp(number of clauses)?

From: sasha mal <sashaDELETEITmal@xxxxxxxxxxxxxxxxxx>
Date: Tue, 11 Jul 2006 19:54:19 +0200

Is there any algorithm to compute #SAT in polynomial time in the number of variables (and exponential in smth. else, e.g. in the number of clauses)?

Regards,
Sasha.
.

Follow-Ups:
- Re: solving #SAT in poly(number of vars) and exp(number of clauses)?
  - From: iatsonios

Prev by Date: Re: Two-dimensional pattern matching/compression
Next by Date: Re: Two-dimensional pattern matching/compression
Previous by thread: Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
Next by thread: Re: solving #SAT in poly(number of vars) and exp(number of clauses)?
Index(es):
- Date
- Thread

Relevant Pages

6P=NP: Proof: Nondeterministic Algorithm
... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... verifies x if there exists a certificate y such ... Algorithm A verifies language L if for any string x Î ...
(sci.math)
Re: Aspiring highest-order programmer
... > that today's programmers repeat the mistakes of the past because their ... not the algorithm choosen to solve it. ... it means that there is no known polynomial time algorithm to ... algorithm to solve any NP-complete problem, ...
(comp.programming)
Re: JSH: Nearly done
... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
(sci.math)
Re: Can EXPTIME and NP be separated via diagonalization?
... where M is a Turing machine and p is a polynomial ... can be done in polynomial time. ... How do we verify that the algorithm we've found solves SAT? ... Consider, for a fixed integer k, the decision problem ALGSAT-k. ...
(comp.theory)
Re: New algorithm for the isomorphism of graphs
... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
(sci.math)