Hacker News Reader

Comment by jrockway | Hacker News Reader

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems.

Everything in the real world is impossible, but we can try and get good results anyway.

View on HN

I believe that the paper argues that this is one of those cases where approximations are not good enough. You cannot read RSA encrypted email with approximate factorization algorithms. You can't forge a document and fool anyone with an approximate SHA collision. I'm not entirely convinced by this analogy but it was made by Appell, and others pointed out in an earlier HN thread that the authors are experts in approximation algorithms.

Sanjeev Arora, paper's coauthor, but also leading expert on approximations to NP-hard problems, has posted a FAQ detailing why he thinks no approximation would help,

http://www.cs.princeton.edu/~rongge/derivativeFAQ.html

And also his response to RJ Lipton who believes approximation ought to work (but then again Lipton believes P=NP, so for him nothing is impossible):

http://rjlipton.wordpress.com/2009/10/22/helping-wall-street...

These are mostly practical reservations, carefully stated as to convince of intractability in the real-world case (which they do) but not prove in theory. Excerpt:

   current pricing and rating algorithms use monte carlo methods
   and would not solve densest subgraphs even for moderate parameters.
   So at the very least those should be changed.

Turns out problem they reduced their model to is open in terms of finding good approximation to it. Excerpt from the FAQ:

   The paper relies upon a stronger form of "P not equals NP", namely,
   that the planted dense subgraph problem does not have an efficient
   algorithm. (In fact it is conjectured that there is no algorithm
   to even compute any approximate solutions to this problem).

>It's also impossible for a traveling salesman to find the best route between cities

It is not impossible, merely Hard.

Which, once translated out of engineering jargon, means "Practically impossible in the general case, assuming you are not willing to accept an approximation."

Exactly. And as the work of this year's Economics Nobel Elinor Ostrom has highlighted, communities often work out cultural norms that resolve difficult coordination and trust issues.

A regulator trying to preempt unfair dealings with rules may have no chance, no matter how wise and disinterested, but people trying diverse strategies over time eventually settle on something that's good enough. (And some scams and business cycles are an inevitable part of that discovery process.)

Reply on news.ycombinator.com