Hacker News Reader

Comment by urgoroger | Hacker News Reader

While I agree with you, you should note that even approximation within any degree of error is NP-complete for a large class of NP-complete problems (e.g. TSP, and the problem MAX-EkSAT used in the paper).

That is, a polynomial algorithm for the approximate problem would be just as significant as one for the exact version.

View on HN

While what you're saying is technically true, you have to be careful with the exact definitions. For many NPC problems, approximations are indeed hard as well, but that a worst case statement. The existence of an algorithm that finds sufficiently good solutions for all instances implies P=NP, but that doesn't mean that there aren't algorithms that find very good approximations for all instances that occur in practice, or for almost all instances that you sample uniformly at random. As long as there is an arbitrarily obscure class of instances left where the algorithm fails to provide a good approximation P!=NP remains a possibility. Experimental evaluations of approximation ratios are not sufficient to claim P=NP.

But that's being NP-Complete, and so can be converted into exact solutions for other NP-Complete problems. Otherwise, by definition, it's not NP-Complete.

So it's not clear what they're actually doing, but if they can solve NPC problems they would say that. So I expect that they are getting approximate solutions that are not then NPC.

That's correct. Given a polynomial time approximate algorithm for Ek-SAT (note, by approximate algorithm I mean along the lines of the formal definition of approximate algorithm, that the solution given by the algorithm falls in some fraction of the real answer for all instances, see https://en.wikipedia.org/wiki/Hardness_of_approximation), you would show P=NP.

My first concerns, namely the usage of analog methods to solve NP-complete problems, lies along the same lines as this post: https://www.scottaaronson.com/blog/?p=2212

Moreover, from what I can see, and as you mention as your original concern, the extent of proof for the 'exponential-speedup' claim exists in the form of some benchmarks, hardly a proof that their method actually works on all instances, which would be needed to show that it is a approximation algorithm as commonly defined.

The purpose of my post was to highlight that for some problems (for example, TSP), even a really crappy approximation algorithm would imply P=NP. As highlighted by the authors of this paper, MAX-EkSAT is in a similar situation, though judging by https://www.cse.buffalo.edu/~hungngo/classes/2006/594/notes/..., unlike TSP, approximation to SOME ratio is possible, though there exists aratio >1 which cannot be beat unless P=NP.

I was simply trying to address the statement: "So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. ", since an actual approximation algorithm for some ratio really WOULD be significant (showing P=NP).

I don't think your first statement is true, there exist polynomial time approximation schemes and approximation algorithms for np complete problems, notably a PTAS for knapsack. In other words, an approximation of one np complete problems doesn't imply an approximation of all of them.

I can't fully articulate the reasons for this though.

The reason for this apparent discrepancy is found in the difference between strong and weak NP-completeness.

The fully polynomial-time approximation scheme (FPTAS) for the knapsack problem only runs in so-called pseudo-polynomial time:

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

This means that the runtime is polynomial in the numeric value of the knapsack. Since the encoding of that numeric value only takes logarithmic space (unless you are using unary encoding), the runtime is in fact again exponential in the size of the input.

For this reason, the knapsack problem is called weakly NP-complete:

https://en.wikipedia.org/wiki/Weak_NP-completeness

One can show that, unless P=NP, a so-called strongly NP-hard optimization problem with polynomially bounded objective function cannot have a fully polynomial-time approximation scheme:

https://en.wikipedia.org/wiki/Polynomial-time_approximation_...

SAT, Hamiltonian circuit etc. are strongly NP-complete:

https://en.wikipedia.org/wiki/Strong_NP-completeness

Thus, an FPTAS for these problems would indeed imply P=NP.

This is a consequence of the PCP theorem, right?

https://en.wikipedia.org/wiki/MAX-3SAT#Theorem_1_(inapproxim...

No. Many approximation problems are known to be NP-hard without relying on the PCP theorem. The PCP theorem is "only" one of the strongest (if not the strongest) and widely applicable result about approximation hardness. (I may be underselling it with this short summary because of the unique games conjecture; in any case, the main point is that there were approximation problems known to be hard long before the PCP theorem was found.)

>TSP

Travelling salesman problem? Can't you get to within a factor of 2 of optimal by constructing a minimum spanning tree:

Once you have a MST (which can be built efficiently), the total weight of the tree is a lower bound for the total distance of a TSP solution. However, you can construct a TSP path that traverses each edge of the MST twice; which means that we know that this path (which is easy to find) is at most twice the total cost of the optimal path.

Your solution works only in metric spaces. In non-metric spaces (distances are arbitrary and you are forced to return a cycle, not a tour that repeats vertices) no constant-factor approximation is possible.

Reply on news.ycombinator.com