SAT Solving + Turing Machines 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?
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").