P VERSUS NP By Farid El Hajj 2012

DESCRIPTION OF P VERSUS NP PROBLEM

Most famous open problem in theoretical computer science. Its solution can deep our understanding of algorithm complexity or maybe it will give us a mathematical tool for solving hard problems in an efficient way. Great work has been spent on providing a solution but no one has ever been able to solve it.

HISTORY
Described in its current form by Cook in 1971 in a paper where he proved the first NP-Complete problem. In 1973 Karp gave another 21 NP-Complete problems. Since then tremendous effort has been deployed to find an algorithm that will reduce any NP problem to P, or on the contrary to prove that these two classes of problems are different.

TECHNICAL IMPACT 

The P versus NP problem has a large impact which makes it a fundamental open problem. Imagine one could derive a polynomial time algorithm for solving an NP-Complete problem, then any NP problem with exponential time could be reduced and solved in a polynomial time in an efficient way. No such algorithm has been found, nor the impossibility to find such a problem has been proved.

LARGER IMPACT

  
If someone could derive such an algorithm the result will have an impact on several domains: theorem proving could be done in an efficient and tractable way. Optimization and resource management will be an easy matter. The impact will be tremendous on many and unthought-of domains such as evolutional biology and economics and much more.
 
If P equals NP then current cryptographic schemes will be broken in a reasonable time and power. The one way functions assumed to be hard could be broken like a piece of toy. But many experts think that P is not equal to NP.

TECHNICAL DESCRIPTION 

The problem belongs to complexity theory. P is the class of problems solved by a deterministic Turing machine in a polynomial time. NP is the class of problems which are solved by a non- deterministic Turing machine in a polynomial time, which means it can be solved by brute force algorithm in an exponential time. Cook in 1971 wrote a paper where he gave the description of the P versus NP problem and he proved that the Boolean satisfiability problem belongs to the NP-Complete class, also he proved that any NP problem could be reduced to an NP- Complete one using a Turing machine in a polynomial time.