Ask an Expert: David S Johnson on NP-complete problems

by: Staff, Tue Oct 09 17:14:00 EDT 2012

What is NP-Complete and why does it matter?


Computers and Intractability: A Guide to the Theory of NP-Completeness

NP stands for nondeterministic polynomial time. So what is that? Let’s break it into two parts:
Polynomial time refers to the time it takes a computer to solve a series of steps, and where the total time is determined by the number of steps; that is, the computing time is a function of the number of steps to the power of some value.
Non-deterministic means the computing time can’t be known from merely adding up the steps.
Computer scientists want to know whether a problem
NP-complete refers to the question of whether nondeterministic polynomial time equals polynomial time.
Essentially the problem boils down to, does the speed of the computer matter in solving the problem?
If it doesn’t matter, than NP does not equal P, and all
One of the great unsolved problems in mathematics is whether NP time equals P (or polynomial time).
Some problems take a computer a long time to calculate [can we give a quick list?]. But are they slow to calculate because the problems are hard, or because the algorithm is inefficient? 
Why does this matter? Because much of Internet security depends NP ≠ P.
If the algorithms are slow only because today’s computers are not fast, quantum computers may quickly solve current NP problems. If it takes a computer today ??years to crack an Internet security code, a quantum computer may be able to do it within minutes. 
If NP does not equal P, Iso many calculations as to be infeasible, even with computers that operated at, say .. the speed of light.
The consensus is that NP does not equal P.

In an NP-complete problem, a particular solution can be verified quickly, but there is no known, efficient way to locate a solution. It could take billions of years.
As one example: You want to tour a number of cities, visiting each city once and returning to the start while traveling less than some fixed number of miles. It’s easy to verify  a  particular route meets the criteria, but it’s hard to find a tour meeting the requirements.

Anyone solving the problem and providing a verified proof is assured fame, and also $1 million courtesy of the  Clay Mathematics Institute in Cambridge, MA, which named "P versus NP" as one of its "Millennium" problems.