3
$\begingroup$

I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:

  • Randomness
  • Heuristics
  • Backtracking

SAT is just one example of an NP-complete problem. Is it common to use such techniques in conjunction to solve intractable problems? I normally see approaches to solving difficult problems in sections, like probabilistic algorithms or parallelism, but what stops them from being employed simultaneously?

Further to this, how is randomness achieved on a Turing machine? I mean by this pseudo-randomness, so is this possible on a Turing machine?

This is a slightly more specific question, but heuristic algorithms will have different meanings based on the problem. So if someone were to make a polynomial-time solver for another NP-complete problem like clique, based on heuristics, how would this also make SAT in P? Basically, certain methods of solving certain NP-complete problems will undoubtedly differ. How can this all at the end of the day reduce to the same problem? Can methods of solving an NP-complete problem be reduced to others?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything at a problem you want to solve. (The reason a book might talk very specifically about say "probabilistic algorithms" instead of "here's how you solve problem X by using a probabilistic algorithm in combination with this trick, that heuristic and this data structure" is that it wants to keep focus on a specific algorithmic idea and its analysis).

The key point here is that a SAT solver is intended to be used in practice, and this is why it makes sense to combine several algorithmic techniques, data structures, etc. to achieve practical efficiency. Still, in general, no matter what the solver does, it cannot be fast and correct on every possible instance (due to NP-completeness).

To understand why having a fast algorithm for an NP-complete problem allows you to solve other such problems, look up polynomial-time reductions, and read up on NP-completeness. Here, again, it is useful to notice that all of this is perfectly fine in theory, but in practice things might be different (it is not true that "polynomial time" necessarily means "efficient in practice").

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks - does this combination of approaches find itself in places other than SAT solving? On the note of Turing machines, I understand that probabilistic machines exist, but are non-deterministic. Is the only 'non-determinism' that it still finds its way to an accept state, or does it incorporate true randomness as well? $\endgroup$
    – Schmetterling
    Commented Aug 3, 2018 at 18:11
  • $\begingroup$ Absolutely, combining algorithms & data structures in smart way is typical when solving problems in practice (this holds even problems that can be solved in polynomial-time). I can't quite tell what your other question is. Perhaps have a look at the definition of a non-deterministic Turing machine or a probabilistic Turing machine. $\endgroup$
    – Juho
    Commented Aug 3, 2018 at 18:16
  • $\begingroup$ True randomness is only important in cryptography. In all other cases, strong enough pseudorandom generators are good enough. $\endgroup$
    – Yuval Filmus
    Commented Aug 3, 2018 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.