P versus NP

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 for a computer to check, though not necessarily easy to solve. For example, if you have an NP problem, and someone says "The answer to your problem is 1 2 3 4 5," 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 "1 2 3 4 5" on its own. In a lot of ways, NP problems are kind of like riddles: it's hard to come up with the answer to a riddle, but once you hear the answer, it sounds obvious (i.e. it's easy to see that it's right and therefore it's also a P problem). The fundamental question is, are riddles really as hard as we think they are, or are we just missing something?

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 other than P problems, or are all NP problems just P problems? If the NP problems are really not the same as P problems (P ≠ NP), it would mean that no general, 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 (P = NP), 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 general, easy methods for solving NP problems yet, many people believe that there are NP problems other than 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. For this reason the question of P versus NP has become an important and widely studied topic.

The question is very tough.

Example[change | change source]

Suppose someone wants to build two towers, by stacking rocks of different mass. One wants to make sure that each of the towers has exactly the same mass. That means one will have to put the rocks into two piles that have the same mass. If one guesses a division of the rocks that one thinks will work, it would be easy for one to check if one was right. To check one's answer, one can divide the rocks into the two piles that one guessed, and then use a balance 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 one has just 100 rocks, there are 2^{100} = 1,267,650,600,228,229,401,496,703,205,376 possible ways to divide these rocks into two piles. For comparison, physicists believe that the universe is about 450,000,000,000,000,000 seconds old. That means that if one takes all of the time that has passed since the beginning of the universe, one would need to check more than 2,000,000,000,000 different ways of dividing the rocks every second, in order to check all of those different ways.

If one programmed a powerful computer to test all of these ways to divide the rocks, it might be able to check 1,000,000 ways per second. This means one would still need 2,000,000 very powerful computers, working since the beginning of time, to test all the ways of dividing the rocks. However, perhaps it is possible for one 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.

Why it matters[change | change source]

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. Here are some examples.

  • 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.
  • 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.
  • 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.
  • A large art gallery has many rooms, and each wall is covered with many expensive paintings. The owner of the gallery wants to buy cameras to watch these paintings, in case a thief tries to steal any of them. He wants to know if 100 cameras will be enough for him to make sure that each painting can be seen by at least one camera.
  • The principal of a school has a list of which students are friends with each other. She wants to find the largest group of students that are all friends with each other.

Exponential Time[change | change source]

In the example above, we see that with 100 rocks, there are 2^{100} ways to partition the set of rocks. With n rocks, there are 2^n combinations. The function f(n) = 2^n is an exponential function. It's important to NP because it models the worst-case number of computations that are needed to solve a problem and, thus, the worst-case amount of time required.

And so far, for the hard problems, the solutions have required on the order of 2^n computations. For any particular problem, people have found ways to reduce the number of computations needed. One might figure out that a way to do just 1% of the worst-case number of computation and that saves a lot of computing, but that is still 0.01 * (2^n) computations. And every extra rock still doubles the number of computations needed to solve the problem. There are insights that can produce methods to do even fewer computations producing variations of the model: e.g. 2^n / n^3. But the exponential function still dominates as n grows.

Consider the problem of scheduling exams (described above). But suppose, next, that there are 15000 students. There's a computer program that takes the schedules of all 15000 students. It runs in an hour and outputs an exam schedule so that all students can do their exams in one week. It satisfies lots of rules (no back-to-back exams, no more than 2 exams in any 28 hour period, ...) to limit the stress of exam week. The program runs for one hour at mid-term break and everyone knows his/her exam schedule with plenty of time to prepare.

The next year, though, there are 10 more students. If the same program runs on the same computer then that one hour is going to turn into 2^{10} hours, because every additional student doubles the computations. That's 6 weeks! If there were 20 more students, then

2^{20} hours = 1048576 hours ~ 43691 days ~ 113 years

Thus, for 15000 students, it takes one hour. For 15020 students, it takes 113 years.

As you can see, exponential functions grow really fast. Most mathematicians believe that the hardest NP problems require exponential time to solve.

NP-complete problems[change | change source]

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. All of the problems listed above are NP-Complete, so 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 solving NP-Complete problems quickly is not possible.

Basic Properties[change | change source]

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties:

  • It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to the problem can be verified quickly (in polynomial time).
  • It is also in the set of NP-hard problems: All NP problems were converted into this single transformation of the inputs in polynomial time. The given solution to the problem is verified quickly, there is found efficient isys to locate solutions in the first place; indeed, the most notable characteristic of NP-complete problems is the fast solutions compound quickly. The time required to solve the problem using an algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether it is possible to solve these problems quickly is found as one of the principal unsolved problems in computer science. Now it could be conjectured the problem is solved by a method for computing the solutions to NP+complete problems using a reasonable amount of remaining time is now discovered: computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer is able to recognize an NP-complete problem so one knowingly spent time trying to solve a problem eluding generations of computer scientists. Instead, NP-complete problems are often addressed by using precision algorithms.

Contextual Properties of NP-complete problems and solutions[change | change source]

Formal overview[change | change source]

NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems solved in polynomial time on a machine. A problem p in NP is also in NPC if and only if every other problem in NP is transformed into p in polynomial time. NP-complete was to be used as an adjective: problems in the class NP-complete were as NP+complete problems.

NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve problem (P). It is found every problem in NP is quickly solved—as called the P = NP: problem set. The single problem in NP-complete is solved quickly, faster than every problem in NP also quickly solved, because the definition of an NP-complete problem states every problem in NP must be quickly reducible to every problem in NP-complete (it is reduced in polynomial time). [1]