Routing is not the same as the Traveling Salesman problem unless you want your packets to go thru all the routers. It's a shortest path problem, which is P. P

Routing is not the same as the Traveling Salesman problem unless you want your packets to go thru all the routers. It's a shortest path problem, which is P. P == NP does not really mean that solving is as easy is verifying the solution. The former could be O(n^4) while the latter O(1). It rather means that if a solution can be verified in a reasonable time (polinomial), then it was also possible to calculate it in a reasonable time.