Re: More beginner questions about SAT...

sasha mal wrote:
My question would be:

is there a SAT solving algorithm working in poly(number of variables n)
and exp(number of clauses m), smth. like O(n^9 * 2^m)?

Regards
Sasha

I'm afraid I'm too much of a beginner to understand the significance of
that question, otherwise I probably would have asked it... ? However,
aren't there already solvers w/ that time complexity anyway?

.

Relevant Pages

  • Re: More beginner questions about SAT...
    ... is there a SAT solving algorithm working in poly ... and exp(number of clauses m), smth. ... I'm afraid I'm too much of a beginner to understand the significance of ...
    (comp.theory)
  • Re: More beginner questions about SAT...
    ... is there a SAT solving algorithm working in poly ... smth. ... There is a variant of SAT called "exactly 1 in 3" SAT where ... the "hard" instances have fewer clauses than variables. ...
    (comp.theory)
  • Re: More beginner questions about SAT...
    ... is there a SAT solving algorithm working in poly ... For each set S of clauses in ascending order: ... information so that one can easily find a satisfying assignment is left ... as an exercise. ...
    (comp.theory)
  • solving #SAT in poly(number of vars) and exp(number of clauses)?
    ... Is there any algorithm to compute #SAT in polynomial time in the number of variables (and exponential in smth. ... e.g. in the number of clauses)? ...
    (comp.theory)