Evidence of exponential speed-up in the solution of hard optimization problems?

Re:Evidence of exponential speed-up in the solution of hard ... by spuz on Wednesday December 27, 2017 @07:02PM (#16019205)

> So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests

The title doesn't suggest anything about exact solutions as far as I can tell.

> We know that for most NP-Complete problems, most instances are easy. The question then is whether they are testing their algorithms on instances that are known to be hard. There's a chance they're doing something like finding factors of random integers, which we know is easy in almost every instance.

I don't know how they choose the problems they choose to solve but I assume this information is in the paper? If you are skeptical then why not read it and report your findings? Simply expressing your skepticism doesn't seem valuable.

[ Parent | on HN ]

Re:Evidence of exponential speed-up in the solution of hard ... by jey on Wednesday December 27, 2017 @08:12PM (#16019531)

> The title doesn't suggest anything about exact solutions as far as I can tell.

In the jargon of mathematical optimization, there's a difference between "solution" and "approximation". The paper's title says "solution". I would expect the title to say something like "2-approximation" or "(1+ϵ)-approximation" instead.

[ Parent | on HN ]