 Bellman (1962) showed that the naive time complexity of \(O(n!)\) for \(\sc{TSP}\) could be improved to \(O(2^n n^2)\) via the use of dynamic programming.  The question thus arose whether it was possible to improve upon such algorithms further, not only for \(\sc{TSP}\), but also for other problem such as \(\sc{SAT}\) for which efficient algorithms had been sought but were not known to exist.  In order to appreciate what is at stake with this question, observe that the naive algorithm for \(\sc{TSP}\) works as follows: 1) enumerate the set \(S_G\) of all possible tours in \(G\) and compute their weights; 2) check if the cost of any of these tours is \(\leq b\). Note, however, that if \(G\) has \(n\) nodes, then \(S_G\) may contain as many as \(n!\) tours.