Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arxiv.org

Post reply on HN
Print view View original

31–40 of 41 posts

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

#31

Post by gizmo686 »

urgoroger wrote: post #13
ColinWright wrote: post #11

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.

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

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

#32

Post by joshuamorton »

urgoroger wrote: post #17
ColinWright wrote: post #15

Earlier quoted context omitted.

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 t…

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.

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

#33

Post by NotOscarWilde »

gizmo686 wrote: post #31
urgoroger wrote: post #13

Earlier quoted context omitted.

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.

>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 mos…

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.

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

#34

Post by godelmachine »

bitL wrote: post #18

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?

Would you kindly provide link to the Berkeley MPC Lab work?

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

#35

Post by bitL »

godelmachine wrote: post #34
bitL wrote: post #18

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?

Would you kindly provide link to the Berkeley MPC Lab work?

Here you go:

http://www.mpc.berkeley.edu/research/analog-optimization

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

#36

Post by zmonx »

joshuamorton wrote: post #32
urgoroger wrote: post #17

Earlier quoted context omitted.

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 t…

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.

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

#38

Post by nhaehnle »

gabrielgoh wrote: post #22
ColinWright wrote: post #11

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.

Yes, and this does indeed mean that their results may be of practical importance.

At the same time, it's pretty well known that the kind of problem instances arising in practice and in those challenges are not hard instances. In other words, this also means that their result is extremely unlikely to be relevant for the P=?NP question.

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

#39

Post by nhaehnle »

moyix wrote: post #30
urgoroger wrote: post #13

Earlier quoted context omitted.

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.

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

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

#40

Post by thesz »

Authors seem not know about this work: https://pdfs.semanticscholar.org/ff7b/3a7b1dad73797ff7c79ac2...

One of the claims in the fine paper that started the discussion is that there's a need to perform several flips at once to find better solution. The paper I cite does something very similar - it walks along chained variables postponing flips until energy lowers for sure.

They also claim their solver has O(vars) time complexity for many problems, including ones with high density (clause/variable ratio). But nothing revolutionary.

Post reply on HN