Wednesday, August 22, 2012

P versus NP problem


Millennium Prize Problems are seven problems in mathematics that were stated by Clay Mathematics Institute in 2000

Out of the 7 problems, one (Poincare conjecture)  problem has been solved

If some one solves any of the problem, he is awarded with US $1,000,000 prize

Poincare conjecture problem was solved by Grigori Perelman on year 2010,  but he declined  to receive the prize.

The seven problems are:
  1. P versus NP problem
  2. Hodge conjecture
  3. Poincare conjecture (solved)
  1. Riemann hypothesis
  1. Yang-Mills existence and mass gap
  2. Navier-Stokes existence and smoothness
  3. Birch and Swinnertori-Dyer conjecture


P versus NP Problem

What is P?

This class of problem are easy to solve. We can have algorithm to solve this type of problem within a reasonable amount of time.

e.g. Check whether a particular number exists in a list.
The simplest solution would be "linear search" algorithm, we check each number in turn until we find the right one.

If the list has n numbers- the "size" of the problem- the algorithm takes at most n steps to search it, so its complexity is proportional to n.

Similarly to do things like manual multiplication of two n-digit numbers, which takes about n2 steps.

Any problem of size n whose solution requires n to the power of something (nx) steps is relatively quick to crack. It is said to be solvable in "polynomial time" and is denoted P.

What is NP?

Not all problems are as easy as P problems.

In some cases, as the size of the problem grows, computing time increases not polynomially as nx, but exponentially as Xn - a much steeper increase.

Imagine, for example, an algorithm to list out all possible ways to arrange the numbers from 1 to n.
Even proving a problem belongs to this non-polynomial class can be difficult, because you have hate to show that absolutely no polynomial-time algorithm exists to solve it.

That does not mean we have to give up on hard problems. With some problems that are difficult to solve in a reasonable time, inspired guesswork might still lead you to an answer whose correctness is easy to verify.

Think of a sudoku puzzle. Working out a solution can be difficult, even for a computer, but presented with completed puzzle, it is easy to check that it fulfills the criteria for being a valid answer.

Problems whose solutions are hard to come by but can be verified in polynomial time make up NP class

Solving a sudoku puzzle is an example of classic NP problem. Process such as using formal logic to check software for errors and deciphering the action of gene regulatory networks are also NP problems



What is P=NP?

All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can we also easily solve it- is every problem in the set NP also in P?