Title: P versus NP problem Content: 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.Juris Hartmanis 1989, Gödel, von Neumann, and the P = NP problem, Bulletin of the European Association for Theoretical Computer Science, vol. 38, pp. 101–107 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.Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), no. 9, pp. 78–86. It is one of the seven Millennium Prize Problems 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^ 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 == 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: * It is in the set of NP (non-deterministic 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: Those which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable. === 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.