P ≠ NP?
23 Nov 2010 Leave a Comment
in Computers and Internet, Reality Tags: complexity classes, computer, P ≠ NP
This is a question that has not been solved for more than 39 years! It was first posed by Stephen Cook. What is P and what is this NP?? P means that a particular problem can be solved in Polynomial time. NP means that it executes in Nondeterministic polynomial time. What does it all mean?? Why is
the Clay Mathematics Institute giving away a million dollars to one who solves this problem?? And what is the relation between this to an Indian who made a lot of news recently?? In this post, I explain the history of this problem, the background of intractability and finally the details of the Indian from HP Labs, Vinay Deolikar’s solution.
Let me illustrate it with a small example…
Consider the subset sum problem in a simple way: You have a collection of billiards balls (15 numbered balls). Someone asks you to pick up balls which add up to 10. Quite simple right? Many solutions exist (10, 1+9, 2+8, 1+2+3+4,etc.) Suppose all even numbers are negative. Then? yes, solutions exist. (7+5-2, 1+3+5+7-6, etc.) But it took more time to answer than the previous one right? This is exactly the problem above. If you can solve it quickly, it can execute in polynomial time. If it cannot, it’s called non-deterministic polynomial. The subset sum problem belongs to the class of NP (quickly checkable) and not necessarily in P (quickly solvable). As the number of balls increases, it cannot provide all of the solutions in any reasonable time.
The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).
In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer’s present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other).
In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine. Clearly, P ⊆ NP. Arguably the biggest open question in theoretical computer science concerns the relationship between those two classes:
- Is P equal to NP?
It is almost impossible to answer the question as it tests the very fundamentals of our assumptions and axioms. To prove that P=NP, one introduces a class called NP Complete which essentially means that the problem can be checked to be NP in polynomial time and that it is in the set NP-hard
Without a mathematical proof, it’s almost impossible to believe anything.
An Indian by name, Vinay Deolikar of HP Labs claim
ed that he had proved that infact P ≠ NP.
It was described as a serious attempt by Markoff and Johnson, 2 leading teachers on computational theory.
The article was then peer-reviewed by the academicians all over the world. \
It was then found to have some irreparable flaws and many concrete errors.
If it had been accepted, it would have created a revolution in the computer industry.
So, we are back to square one again. 
To find out more about Complexity classes, chek out the zoo!!
