In this blog post the focus will be on the P vs. NP problem.
This problem is easy enough to explain in a post, but the real world
applications of this problem are much too vast to be covered in a single post.
So the main focus will be on the problem, and a few of its applications. First
the problem, then how it relates solving Sudoku puzzles to curing cancer.
The P vs.
NP problem arose in the 1970’s. This is the time period when advances in
computer technology were starting. At the time computer scientists realized
that some problems were easier to compute then others. For example, a computer
could do multiplication within a small amount of time, but could not compute the next perfect chess move in a timely manner. Computer scientists started
grouping these problems as P and NP problems. Focusing first on P problems, P
problems refers to problems that a program can solve in a reasonable amount of
time, such as multiplication, or alphabetizing a given set entry of names. Then
outside P problems, but still including P problems, is another category called
NP problems. The NP problems are problems that take a long time to solve, but
can be easily checked if given the solutions. A common example of this is a
Sudoku puzzle. It takes a reasonable amount of time to solve a Sudoku, but it
only takes seconds to check to see if the solution is valid. Now Sudoku puzzles
have become easy to solve with the advancement of computers, but that does not
change it to being a P problem. P stands for polynomial time, meaning the
time in order to solve the problem, can written as a polynomial function. For
example, going to back to multiplication, the bigger the numbers being
multiplied get, the more time it takes to solve the problem. However, the time that it
takes to solve then can be given as a polynomial function, like x^2 or x^3,
meaning that the relation can be described using polynomials. NP refers to
Non-deterministic polynomial time. This means that the amount of time it takes
to solve a problem cannot be written as a polynomial function. Going back to
the Sudoku problem, if the size of Sudoku board is scaled up the time taken to
solve goes up exponentially and becomes difficult even for super computers. P
problems are a sub category of NP problems, and over time computer scientists
have found that some of the formerly thought NP problem were P problems. This
is obviously not the case for all problem because then there would be no P vs.
NP, but the idea that one day all NP problems will become P problems is a
possible theory. This is a bit of controversy in computer science. Some
computer scientists and mathematicians think that P will one day equal NP,
meaning all NP problem will become P problems, and others think they will
remain separate. This is the P vs. NP problem, can all NP problems become P
problems, or will they remain as they are. The main problem with this problem,
is the P vs. NP problem is an NP type problem in itself. That makes the problem
tricky unless, it can actually become a P problem.
There is
another sub group, in fact there are many other grouping, but the focus is on the NP complete sub group. NP complete refers to root NP problems. In
1970’s computer scientists found that the NP problems were all the same kinds of
problems with a little bit of variance. These root problems connect all the NP
problems, and if they can be turned into P problems then all NP problems can
change to P problems. In the 1970’s a grouping was released, but since then
additions to the list include: Sudoku, Tetris, protein folding, and even
crossword puzzles. Protein folding problems are apart our understanding of
curing cancer, so it means that if there is a faster way found to simplify
solving Sudoku puzzles, it could lead to the curing of cancer. This is why P
vs. NP problem is such a big deal. This is why the P vs. NP problem is a
Millennial prize problem. If it can be solved there is a possibility that the
world around us could change immensely. There is also the possibility that it
will not, if the NP and P problem remain separate. The point is no one knows, and it
would be worth finding out.
No comments:
Post a Comment