P versus NP

tsp

P versus NP is the name of a question that many mathematicians, scientists, and computer programmers want to answer. P and NP are two groups of mathematical problems. P problems are considered ‘easy’ for computers to solve. NP problems are easy only for a computer to check.

For example, if you have an NP problem, and someone says ‘The answer to your problem is 12345,’ a computer can quickly figure out if the answer is right or wrong, but it may take a very long time for the computer to come up with ‘12345’ on its own. All P problems are NP problems, because it is easy to check that a solution is correct by solving the problem and comparing the two solutions. However, people want to know about the opposite: Are there any NP problems that are not P problems, or are all NP problems just P problems?

If the NP problems are really separate from the P problems, it would mean that no fast and easy ways to solve those NP problems can exist, no matter how hard we look. However if all NP problems are P problems, it would mean that new, very fast problem solving methods do exist, but we haven’t found them yet. Since the best efforts of scientists and mathematicians haven’t found the easy methods for solving NP problems yet, many people believe that there are NP problems that are not P problems. Most mathematicians also believe this to be true, but currently no one has proven it by rigorous mathematical analysis. If somehow it is proven that NP and P are the same, it would have a huge impact on many aspects of our life; computer problems that take years to compute could be solved instead in seconds. For this reason the question of P versus NP has become an important and widely studied topic.

Suppose a woman wants to build two towers, by stacking rocks of different mass. She wants to make sure that each of the towers has exactly the same mass. That means she will have to divide the rocks into two piles that have the same mass. If she guesses a division of the rocks that she thinks will work, it would be easy for her to check if she was right. To check her answer, she can divide the rocks into the two piles that she guessed, and then use a scale to see if they have the same mass. Because it is easy to check an answer to see if it is correct, this problem, called ‘Partition’ by computer scientists, is an NP problem. If she has just 100 rocks, there are possible ways to divide these rocks into two piles.

For comparison, physicists believe that the universe is about seconds old. That means that if the woman took all of the time that has passed since the beginning of the universe, she would need to check more than different ways of dividing the rocks every second, in order to check all of those different ways. If the woman programmed a powerful computer to test all of these ways to divide the rocks, it might be able to check ways per second. This means she would still need very powerful computers, working since the beginning of time, to test all the ways of dividing the rocks. However, perhaps it is possible for her to find a method of dividing the rocks into two equal piles without checking all combinations. The question ‘Is P equal to NP?’ asks if any method like that exists. This question is so important that the Clay Mathematical Institute will give $1,000,000 to anyone who answers it.

There are many important NP problems that people don’t know how to solve in a way that is faster than testing every possible answer. For example: A travelling salesman wants to visit 100 different cities by driving, starting and ending his trip at home. He has a limited supply of gasoline, so he can only drive a total of 10,000 kilometers. He wants to know if he can visit all of the cities without running out of gasoline. Or, a school offers 100 different classes, and a teacher needs to choose one hour for each class’ final exam. To prevent cheating, all of the students who take a class must take the exam for that class at the same time. If a student takes more than one class, then all of those exams must be at a different time. The teacher wants to know if he can schedule all of the exams in the same day so that every student is able to take the exam for each of their classes. Or, a farmer wants to take 100 watermelons of different masses to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market.

Mathematicians can show that there are some NP problems that are NP-Complete. An NP-Complete problem is at least as difficult to solve as any other NP problem. This means that if someone found a method to solve any NP-Complete problem quickly, they could use that same method to solve every NP problem quickly. The salesman and scheduling problems are NP-Complete; if the salesman found a way to plan his trip quickly, he could tell the teacher, and she could use that same method to schedule the exams. The farmer could use the same method to determine how many boxes she needs, and the woman could use the same method to find a way to build her towers. Because a method that quickly solves one of these problems can solve them all, there are many people who want to find one. However, because there are so many different NP-Complete problems and nobody so far has found a way to solve even one of them quickly, most experts believe that it is not possible to find the answers to any of them quickly.

According to polls, many computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a significantly faster algorithm for any of more than 3000 important known NP-complete problems. These algorithms were sought long before the concept of NP-completeness was even defined. It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience. According to Scott Aaronson of MIT, ‘If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…’

On the other hand, some researchers believe that there is overconfidence in believing P ≠ NP and that researchers should explore proofs of P = NP as well. For example, in 2002 computer scientist Moshe Y. Vardi said, ‘The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [. . .] The resolution of Fermat’s Last Theorem also shows that very simple questions may be settled only by very deep theories.’ Mathematician Anil Nerode adds, ‘Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.

One of the reasons the problem attracts so much attention is the consequences of the answer. Either direction of resolution would advance theory enormously, and perhaps have huge practical consequences as well. A proof that P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice. The consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields. Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems including public-key cryptography, a foundation for many modern security applications such as secure economic transactions over the Internet, and symmetric ciphers such as AES or 3DES, used for the encryption of communications data. These would need to be modified or replaced by information-theoretically secure solutions.

On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming, and the travelling salesman problem, to name two of the most famous examples. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete; if these problems were efficiently solvable it could spur considerable advances in biology. But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself.

According to Stephen Cook: ‘…it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.’ Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated—for instance, Fermat’s Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a ‘reasonable’ size, would essentially end this struggle.

A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.

Also P ≠ NP still leaves open the average-case complexity of hard problems in NP. For example, it is possible that SAT requires exponential time (NP) in the worst case, but that almost all randomly selected instances of it are efficiently solvable (P). Russell Impagliazzo has described five hypothetical ‘worlds” that could result from different possible resolutions to the average-case complexity question. These range from ‘Algorithmica,’ where P = NP and problems like SAT can be solved efficiently in all instances, to ‘Cryptomania,’ where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The ‘world’ where P ≠ NP but all problems in NP are tractable in the average case is called ‘Heuristica’ in the paper.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s