After almost 20 years, math problem falls

http://www.physorg.com/news/2011-07-years-math-problem-falls.html

by ph0rque • 15 years ago

69 15 15 years ago

rabedik• 15 years ago

"For an arbitrary polynomial function [...] determining whether it’s convex is what’s called NP-hard. That means that the most powerful computers in the world couldn’t provide an answer in a reasonable amount of time."

eye twitch

A problem's complexity class only gives an indication of potential runtime. There are decent algorithms for a lot of NP-complete problems (airline/package routing, compiler backend optimizations, etc.) that don't require "the most powerful computer in the world". I'm pretty sure the correct definition of hardness/completeness in complexity theory can be boiled down to a sentence that's much more correct than that, especially if you include something like "at least as hard as all other NP problems"

ars3• 15 years ago

In math (well, in proofs) an answer must be "the" answer, a good enough answer is not good enough.

Those algorithms you mention provide reasonable answers, but they do not guarantee that the answer is the best answer.

saulrh• 15 years ago

Well, a lot of them can approximate "the" answer to within an arbitrarily and provably small amount, so it's definitions. For example, there is a polynomial-time approximation for euclidean TSP that produces a solution with length at most (1 + epsilon) * optimal.

Groxx• 15 years ago

That's nuttery. Borderline hero-worship. There are loads of epsilon-accurate proofs in math. Similarly, there are loads of non-perfect-but-more-efficient algorithms in CS.

mturmon2• 15 years ago

Your last statement is incorrect for one of the problems mentioned in the parent comment ("airline/package routing" which I take to be linear programming problems).

Simplex-type algorithms are typically used for these problems. These algorithms also have exponential time complexity in worst-case. In practice, well-designed simplex algorithms are of low-order-polynomial complexity. They terminate with an exact optimum.

This case, and others, are examples of situations where conventional complexity analysis fails to provide insight into real-world performance.

Last I knew, people were trying to analyze expected time complexity of certain (analysis-friendly) simplex algorithms under distributional constraints on the input structure matrices. But it's important to understand that this is mathematical back-filling to explain what is already known to hold in practice.

radarsat1• 15 years ago

Let me take a crack at it:

"... is what's called NP-hard. That means that finding the answer is at least as hard as cracking a very strong cryptographic key, something that is currently considered too computationally expensive to be practical."

Would that be a better explanation, understandable by the article's target audience?

stevetjoa• 15 years ago

How pleasantly surprised I am to find that the work of Amir Ali Ahmadi, a friend and former student at Maryland where I was his EE TA, appeared on Hacker News. We both took the same graduate-level class on optimal control; despite being an undergrad, he was one of the best students in the class.

The result is intriguing and reasonably accessible: for all (multivariate) polynomials whose degrees are even and at least four, determining convexity (of any type! strong, strict, regular, pseudo-, quasi-) is strongly NP-hard. To prove this, the authors equate the problem of determining convexity to the problem of determining the nonnegativity of biquadratic forms -- a known NP-hard problem.

Find the paper here: http://aaa.lids.mit.edu/publications. (Edit: direct PDF link http://mit.edu/~a_a_a/Public/Publications/convexity_nphard.p...) See Table I on page 18 for a concise summary.

gjm11• 15 years ago

Like most things on physorg, this is blogspam. The original is at http://web.mit.edu/newsoffice/2011/convexity-0715.html and (unlike the physorg version) includes links to more detailed information about the research.

podperson• 15 years ago

It's also badly written, buries the lead, and exaggerates the solution (which is that the math problem didn't fall, but a simpler problem which is almost as useful did.

seagaia• 15 years ago

Another one added to the NP-hard list, mhm.

Maybe some things to clear stuff up:

NP-complete is a subset of NP-hard. NP-complete is entirely in NP, not all NP-hard are in NP.

After almost 20 years, math problem falls

Related Stories