4 ms·
> I have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful avai
by throwawaylinux 5y ago
> I have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful available information.
Not sure what you're getting at here. The available useful information is a set of cities each with distances to the other cities. About N^2 pieces of information. A computer can "utilize" all these data in polynomial time.
- whatever1 5y agoThe information needed to solve the tsp problem is not the distances matrix. It’s the set of Hamiltonian paths in your graph. And that scales factorially with the number of cities. It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.
- gizmo686 5y agoAll the information about the Hamiltonian paths is encoded in your N verticies and N^2 edges. Your arguement suggests the best solution to TSP runs in Θ(n!). However https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm can solve TSP in Θ(2^n n^2)
- whatever1 5y agoWhich means that many of Hamiltonian paths are strictly dominated than others, so you don’t have to evaluate them at all. Same as in sorting you don’t have to evaluate all of the possible pairs. I did not imply that all information is useful. I proposed that probably there is a lower bound of information that you definitely need to find the optimal solution to the tsp.