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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.