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.
Think of a huge jigsaw puzzle. You might have thousands of pieces that could each go in thousands of possible places, and while you may know tricks to speed up the process, solving it would surely take a lot of trial and error and time. When you did finally solve the puzzle, though, it would only take you a moment to check the picture against the box and prove your solution was correct. That makes it a NP problem.
Another jigsaw puzzle has every piece labeled with column and row, so you can put the whole thing together in one sweep—no trial and error needed. Both solving the puzzle and verifying the solution would be simple. That makes it a P problem.
If P=NP, it would indicate the first jigsaw puzzle has labels on its pieces too, just harder to see. If you can find them, solving the puzzle becomes trivial.
There are a great number of NP problems in the world; if P=NP we could find the solutions to many intractable math problems within our grasp.
.
Unfortunately, one of those is encryption. Many encryption methods use a NP math problem as a lock and its solution as a key. We assume it would take an impractical amount of time to solve the math problem, so the only way in is by knowing the solution. But if P = NP, breaking that lock (by solving the math) could become as fast as using the key. Oops!
How can I believe you when you tell me what I don't want to hear?