4 ms·
This is a non story, at least insofar as it concerns complexity. The result would be no more or less interesting if the amoebas sorted an array or did some othe
by emtel 8y ago
This is a non story, at least insofar as it concerns complexity. The result would be no more or less interesting if the amoebas sorted an array or did some other polynomial time task. Here's why:
1. Finding approximate or near-optimal solutions for hard optimization problems is almost always easy. So in this case, an amoeba did something that is also easy to do with a classical computer.
2. 8 is a small number. There are 8! possible paths, which is about 40,000, which means you could find the optimal solution to this problem in a millisecond or two with a classical computer. To be remotely interesting, you'd need to solve a TSP for a number like, say, 50 or 100.
3. Even if you had an amoeba that somehow could find solutions for large numbers of cities, how would you know? You can't solve the problem instance yourself, so you don't know how close it is to the optimum. This is because TSP is not in NP, which are the set of problems whose solutions can be verified in polynomial time. Rather, its NP-hard, meaning its at least as hard as any NP problem, but its solutions can't be verified in polynomial time. So if amoebas had some magic TSP solving algorithm, we probably wouldn't be able to tell that they did unless we had our own magic algorithm to test it against.
4. Also, even if the amoeba could solve this optimally for large instances, _most_ instances of hard problems are actually easy. Therefore, simply showing that the amoebas can do this for some finite number of instances is not sufficient. An efficient algorithm for TSP or some other hard problem has to be able to solve _any possible instance_ efficiently, in order for this to have any implications for questions like P=NP. So if you wanted to show that amoebas had a magic TSP algorithm, you'd have to formally prove that their algorithm works on all instances. Since amoebas themselves are not easily formalizable, I don't see how you'd do this.
- algorias 8y ago>> This is because TSP is not in NP Um, the decision version of TSP (does there exist a Hamilton path of length at most x?) is definitely in NP. It is also NP-hard (your definition of NP-hardness is wrong). I guess what you're trying to say is that the optimization version of TSP (find the shortest Hamilton path) cannot be verified in polynomial time, as this would require answering the decision version of TSP in the negative for some length x, and this is hard to verify since TSP is not in co-NP. In spirit, your comment is absolutely spot on. But as we all know, technically correct is the best kind of correct :)
- emtel 8y agoBut the article isn't talking about the decision TSP, is it, so your objection doesn't apply?
- deleted 8y ago[deleted]
- jeromebaek 8y ago> You can't solve the problem instance yourself, so you don't know how close it is to the optimum. This is wrong. "the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems." (https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem) If amoeba gives me a proposed solution to the TSP, I can easily check if said amoeba is right or wrong. You are right that I don't know how close it is but I know if it's right or wrong. And this should be enough because we already have close-enough approximations of the TSP. Also your definition of NP-hard is wrong: you're right that it is "at least as hard as any NP problem" but the conjunction of this with "its solutions can't be verified in polynomial time" is false, because the definition of a NP problem is that its solutions can be verified in polynomial time. Also, this is not interesting because problem instance is small is not always a good argument. An implementation of a quantum algorithm factoring 15 into 5 and 3 is interesting, even though it is trivial.
- emtel 8y agoMy definition isn't wrong - NP-hard is a superset of NP. There are problems in NP hard whose solutions can't be verified in polynomial time. Also, you're wrong about being able to verify a solution easily. The decision version of the TSP is NP-complete, which means you can't solve it efficiently unless you can solve NP complete problems. You're confusing _solving_ the decision problem with _verifying a solution_ to the decision problem.
- jeromebaek 8y agoEither we are talking past each other or you are confused. A solution to the decision version of the TSP can certainly be verified in polynomial time.