The theory of computation studies a class of problems called ‘NP Complete.’ These are problems that are considered computationally hard in the sense that all known algorithms to solve them require a non-deterministic Turing machine polynomial orders of time. The traveling salesman problem is a classic example of this set. They all share one characteristic – indeed it is the test of membership in the class – that they are all isomorphic. An algorithm that solves any of the problems would therefore solve all of NP Complete problems.
Continue reading →