P versus NP

Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP are the two types of maths problems referred to: P problems are 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.

#1 problem in Computer Science

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.[[3]](https://simple.wikipedia.org/wiki/P_versus_NP#cite_note-3) It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.

Why?

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 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.
  • The clique problem: The principal of a school has a list of which students are friends with each other. She wants to find a group of 10% of the students that are all friends with each other.

Source

  • https://simple.wikipedia.org/wiki/P_versus_NP
  • http://www.claymath.org/millennium-problems/p-vs-np-problemSources