Hacker News Reader

I was just thinking on the TSP the other night, would a practical application of this problem(and solution) be to use it in processor circuit layout and trace routing? Then using the improved processor to solve the problem again?

View on HN

Maybe, but a real challenge of circuit layout and routing is that you want to generate (mostly) planar graphs, since your options for intersecting connection lines are limited and expensive. For the TSP, this does not really matter since the problem is more abstract.

Interesting point, TBH I had never considered applying the TSP to any more than two dimensions, as it becomes exponentially more difficult with each node added even within the same plane. I'm not even sure if adding more dimensions would make it more difficult or not but You have me thinking on that now, so thank You.

probably

circuit satisfiability and related hard problems are all reducible to each other

Reply on news.ycombinator.com