Slashdot Mirror
New Algorithm Provides Huge Speedups For Optimization Problems (mit.edu)
An anonymous reader writes: MIT graduate students have developed a new "cutting-plane" algorithm, a general-purpose algorithm for solving optimization problems. They've also developed a new way to apply their algorithm to specific problems, yielding orders-of-magnitude efficiency gains. Optimization problems look to find the best set of values for a group of disparate parameters. For example, the cost function around designing a new smartphone would reward battery life, speed, and durability while penalizing thickness, cost, and overheating. Finding the optimal arrangement of values is a difficult problem, but the new algorithm shaves a significant amount of operations (PDF) off those calculations. Satoru Iwata, professor of mathematical informatics at the University of Tokyo, said, "This is indeed an astonishing paper. For this problem, the running time bounds derived with the aid of discrete geometry and combinatorial techniques are by far better than what I could imagine."
To give a brief and hopefully laymen-friendly explanation:
It isn't an equation per se; P and NP are classes of computational problems. Roughly speaking, P is the set of problems that can be solved deterministically in polynomial time with respect to some input parameter, and NP is the set of problems that can be solved non-deterministically in polynomial time with respect to some input parameter (hence the "N"). A more approachable definition of NP for laymen is that it comprises problems for which a solution can be verified (or rejected) in polynomial time. For instance, prime factorization of an integer is in NP because, given an input integer and a list of prime factors, you can verify that the list is actually the prime factorization of the integer in polynomial time (by multiplying them together).
The significance, aside from pure theoretical interest, is that a lot of very interesting practical problems are known to be in NP, and knowing that those problems could be solved in polynomial time would be very useful.