Where it is feasible is, when no other fast algorithm is known, such as the puzzle you mention. So, yes, SAT can be used for all these problems you are mentioning. TSP is another NP-Complete problem, but the transformations are most often much more difficult. you can solve it instead of any other problem in NP, and also the reductions are not so hard to do. SAT is so nice, because it is NP-Complete, i.e. Often however it can be proven that a problem is NP-Complete, but the transformations are unclear for another given problem. This means you can transform a problem from one domain into another NP-Complete problem, have it derive an answer and transform the answer back.
This set contains all problem which are so generic, you can solve these Problems instead of another one from NP (this is called reducing a problem onto another). Then there is the set of NP-Complete problems. Unless the problem is in the P part of NP of course (as pointed out below P is part of NP, as you can easily verify).
This means veryfing a given solution is fast, but finding one is usually slow (most often exponential time). NP is the class of all problem for which a solution can be verified in polynomial time. P is the class of all problems which can be solved in polynomial time (i.e. To understand what this means you need a clear notion of Complexity classes. SAT is very important because it is NP-Complete.
0 kommentar(er)
