A Quick Overview of P vs. NP Problems

Date: 11/19/2007 at 17:01:40
From: Zach
Subject: P vs. NP

What exactly is the P vs. NP property, and why is it so important?

I have not been able to find an answer at a high school mathematics
level.  I find the high-level mathematical answers to my question that
are on the internet too in-depth for my level of understanding.

I think it has something to do with the idea that some problems have
no formula, and must instead be solved through "labor."  That's about
all I know.

Date: 11/19/2007 at 19:31:11
From: Doctor Tom
Subject: Re: P vs. NP

Hi Zach,

I'm afraid it does require more than high school mathematics to
understand exactly what it means, but maybe I can help a little.

Certain classes of problems concern arbitrary amounts of data.  For
example, a very simple problem is this: given n numbers, find the
largest.  You can find the largest simply by looking through and 
keeping track of the largest so far, so when you get to the end of the 
list, you'll know the answer.  If I give a computer a list of 1000
numbers, it'll take a certain amount of time to find the largest.  If
I give it 10 times that many numbers, it will take it 10 times as
long, et cetera.

A harder problem is to sort into increasing order an arbitrary list of
n numbers.  If I give a list that's 10 times as long, it will, in
fact, take a bit more than 10 times as long to sort it, but not
outrageously more.  Likely, it will take about 10 x log(10) times as
long, roughly.

Computer scientists classify problems by how long it takes to solve
them in terms of the size of the problem.  For the first one, it'll
take time proportional to n; for the second, it takes time
proportional to n log(n).  Other types of problems can be much harder.

Computer scientists have a definition for problems that can be solved
"reasonably fast", and they call it "P".  This stands for "polynomial
time", and it means that the problems can be solved in time that is
proportional to some polynomial function of n.

There is a very large list of VERY interesting and important problems
that nobody knows how to solve in polynomial time, and, even more
interesting, if ANY of them can be solved in polynomial time, then
they ALL can.  And many very smart people have been looking for 
a fast method to solve many of the problems, and nobody has ever
succeeded.

So one suspects that these problems (for example, the "traveling
salesman problem") are NOT in P.  But on the other hand nobody has been
able to prove that any of the problems is NOT in P!

These problems (for technical reasons) are called NP problems ("NP"
stands for "non-deterministic polynomial"), so one of the hardest and
most important problems in computer science is, "Is P = NP?"  In other
words, are the NP problems solvable in polynomial time?  Probably not,
but nobody knows.

There are some solutions to NP problems, of course, but they run in
far more than polynomial time.  For example, you can solve the
traveling salesman problem by simply trying all possible routes and
picking the shortest.  But if the salesman has to visit n cities, 
there are n! (n factorial) routes, and n! increases much faster than
any polynomial in n.

I hope this helps!

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/