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:
- P versus NP problem
- Hodge conjecture
- Poincare conjecture (solved)
- Riemann hypothesis
- Yang-Mills existence and mass gap
- Navier-Stokes existence and smoothness
- 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?
Comments
Post a Comment