P versus NP problem

P versus NP is one of the Millennium Problems, and of great interest to people working with computers and in mathematics. One way of asking it is, "Can every solved problem whose answer can be checked quickly by a computer, also be quickly solved by a computer?" Math problems are referred to as P or NP, whether they are solvable in finite polynomial time. P problems have their solution time bound to a polynomial and so are relatively fast for computers to solve, and so are considered "easy". NP problems are fast (and so "easy") for a computer to check, but are not necessarily easy to solve.
In 1956, Kurt Gödel wrote a letter to John von Neumann. In this letter, Gödel asked whether a certain NP complete problem could be solved in quadratic or linear time. In 1971, Stephen Cook introduced the precise statement of the P versus NP problem in his article "The complexity of theorem proving procedures".
Today, many people consider this problem to be the most important open problem in computer science. It is one of the seven selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for a solution that invites a published recognition by the Clay Institute, and presumably one(s) that changes the whole of mathematics.
Because many of these problems touch upon related issues, and it is the dream of many mathematicians to invent unifying theories, many hope the Millennium Problems are interconnected.
Clarifications.
A computer may be able to tell if an answer is right, but take longer to get the answer. For some interesting, practical questions of this kind, difficult answers are possible to check quickly. So NP problems may be thought of as being like riddles: it may be hard to come up with an answer to a riddle, but once one hears the answer, the answer seems obvious. In this comparison (analogy), the basic question is: are riddles really as hard as we think they are, or are we missing something? Is there a secret to always having an answer?
Because these kinds of "P versus NP" questions are so practically important, many mathematicians, scientists, and computer programmers want to prove the general proposition, that every quickly-checked problem can also be solved quickly. This question is important enough that the Clay Mathematical Institute will give $1,000,000 to anyone who successfully provides a proof or a valid explanation that disproves it.
Digging a little deeper, we see that all P problems are NP problems: 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 NP problems are really not the same as P problems (P ≠ NP), it would mean that no general, fast 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. We just have not found them yet.
Since the best efforts of scientists and mathematicians have not found general, easy methods for solving NP problems yet, many people believe that there are NP problems other than P problems (that is, that P ≠ NP is true). Most mathematicians also believe this to be true, but currently no one has proven it by rigorous mathematical analysis. If it can be proven that NP and P are the same (P = NP is true), it would have a huge impact on many aspects of day-to-day life. For this reason, the question of "P versus NP" is an important and widely studied topic.
Example.
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 the answer, one can divide the rocks into two piles, then use a balance to see if they have the same mass.) Because it is easy to check this problem, called 'Partition' by computer scientists—easier than to solve it outright, as we will see—it is not a P problem.
How hard is it to solve, outright? If one starts with just 100 rocks, there are 2^{100-1}-1 = 633,825,300,114,114,700,748,351,602,687, or about 6.3 x 10^{29} possible ways (combinations) to divide these rocks into two piles. If one could check one unique combination of rocks every day, it would take 1.3 x 10^{22} or 1,300,000,000,000,000,000,000 years of effort. For comparison, physicists believe that the universe is about 1.4 x 10^{10} years old (450,000,000,000,000,000 or about 4.5 x 10^{17} seconds, or about one trillionth as old as the time it would take for our rock piling effort. 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 two trillion (2,000,000,000,000) different ways of dividing the rocks "every second", in order to check all of the different ways.
If one programmed a powerful computer, to test all of these ways to divide the rocks, one might be able to check formula_1 combinations per second using current systems. This means one would still need formula_2 very powerful computers, "working since the origin of the universe," to test all the ways of dividing the rocks.
However, it may be possible to find a method of dividing the rocks into two equal piles without checking all combinations. The question "Does P equal NP?" is a shorthand for asking if any method like that can exist.
Why it matters.
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:
Exponential Time.
In the example above, we see that with formula_3 rocks, there are formula_4 ways to partition the set of rocks. With formula_5 rocks, there are formula_6 combinations. The function formula_7 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 formula_6 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 formula_9 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. formula_10. But the exponential function still dominates as formula_5 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 formula_12 hours, because every additional student doubles the computations. That's formula_13 weeks! If there were 20 more students, then
Thus, for formula_18 students, it takes one hour. For formula_19 students, it takes formula_17 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.
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.
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties:
Formal overview.
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). 
Examples.
The Boolean satisfiability problem is known to be NP complete. In 1972, Richard Karp formulated 21 problems that are known to be NP-complete. These are known as Karp's 21 NP-complete problems. They include problems such as the Integer programming problem, which applies linear programming techniques to the integers, the knapsack problem, or the vertex cover problem.