> 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, giv

> 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.