Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most…
I was only skimming the article, but it seems they were comparing against benchmarks form this contest:
Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most…
they did experiments on the 2016 Max-SAT challenge, which seems to me like a legitimate class of problem instances.
Is this similar to what Berkeley MPC Lab is doing with quadratic programming using electricity? I.e. that nature has means to solve optimization problems in an instant and our approximations of this process in the form of differential equations allow us to do something similar, albeit not 100% accurately?
Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most…
> 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 li…
> 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.
Looking at the authors papers it doesn't look worth reading.
What do you mean? How does that help you to decide if a paper is worth reading or not?
IF the authors have a history of poor work, or no history at all, or a bunch of stuff that has been discredited, then the likelihood that they have solved a big problem declines.
People who do massively important work typically telegraph quality by doing earlier good work. That isn't always true, but it is commonly true.
What do you mean? How does that help you to decide if a paper is worth reading or not?
IF the authors have a history of poor work, or no history at all, or a bunch of stuff that has been discredited, then the likelihood that they have solved a big problem declines. People who do massively important work typically telegraph quality by doing earlier good work. That isn't always true, but it is commonly true.
You could say that estimating a paper's worth by the quality of the authors' previous papers is an approximate solution to the NP-hard "paper quality assessment" problem, which offers an exponential speed-up. :P
This keeps popping up every few months for several years, and seems like BS. Here's an example: https://news.ycombinator.com/item?id=8652475 And here's Scott Aaronson's debunking: https://www.scottaaronson.com/blog/?p=2212 If these guys could really solve NP complete problems, they should have some amazing concrete results to show at this point, which they don't.
You link to research from 3 years ago. Does the latest paper (Oct 2017) not represent the concrete results you claim they don't have?
They claim to solve np complete problems, which this paper is not demonstrating.
Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most…
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.
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.
Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most…
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.