Hacker News new | ask | show | jobs
by vecter 5811 days ago
I'm not sure if quarks have "positions" in the exact sense of the word, so I don't think there's a metric you could apply here to get distances for which to solve TSP.

Suppose there was a metric between quarks. To be clear, are you saying: take all quarks in the universe. Take their powerset P. For each set S in P, create the complete graph K_{|S|} where edge lengths are distances. Let TSP(x, K_{|S|}) be the number of steps required to solve TSP. Sum TSP(K_{|S|}) for all S in P.

Let n be the number of quarks in the universe. The size of the powerset is 2^n. For each S in P, since TSP is solvable in exponential time, we'll upper bound the number of steps by 2^n. In other words, for each powerset, you're cost for solving TSP is at most 2^n. Therefore, the number of steps is at most 2^n * 2^n = 2^(2n), which is far smaller than say Ackermann(6, 6).

1 comments

Touche.