## Another possible solution to an NP-complete problem?

A couple of days ago a research team comprised of faculty at Nanyang Technological University in Singapore, the University of Southampton in the UK, and IQFR-CSIC in Madrid, Spain published a paper containing a creative solution to a problem known to be NP-complete, namely a version of the traveling salesman problem. The TSP, in summary, postulates a scenario in which you have an arbitrary number of towns spread over a large area and an arbitrary number of paths connecting them. What is the shortest possible path one can take in which the traveler visits each town only once and returns …

Read more...