What are NP problems?

Question

I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems?

Answer 1

NP problems are problems that given a proposed solution, you can verify the solution in a polynomial time. For example, if you have a list of University courses and need to create a schedule so that courses won't conflict, it would be a really difficult task (complexity-wise). However, given a proposed schedule, you can easily verify its correctness.

Another important example from the field of encryption: given a number which is the result of multiplying two very large prime numbers, it's very difficult to find those primes based only on the result. However, given two numbers, it's very easy to check the solution (multiply them, compare).

I have intentionally chose examples that are in NP and not in P (i.e. problem that are hard to find the solution for) so you can understand the difference. All problems that are easy to solve, are also easy to verify - just solve and compare. That is, P is a subset of NP.

Answer 2

Not really an answer, because Piccolo's link is more useful, but a HP researcher claims having proven P != NP, here is the paper.

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

It was not accepted yet, but I wish him good luck for the 1M$.