Vinay Deolalikar at HP Labs claim to have proved that P != NP . According to his paper…polynomial time algorithms succeed by successively “breaking up” the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes where blocks whose order is the same as the underlying problem instance require simultaneous resolution. As anyone could predict, the alleged proof of one of the thorniest problems in CS has already been Slashdotted. As i’m not a hardcore mathematician, i’ll not go into details of this…but what is this P vs NP thing all about…lets explore !!
First of all P stands for polynomial time. NP stands for non-deterministic polynomial time. As the name implies, Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data and k is a constant.Complexity is time measured in the number of operations(e.g. comparisons in case of sorting) it would take, as a function of the number of data items. Now we basically narrowed our discussion to deterministic vs non deterministic (gosh…i luv abstraction) . There is an abstract computational model, an imaginary computer called a Turing machine (TM).A Turing machine is a kind of state machine. At any time the machine is in any one of a finite number of states. Instructions for a Turing machine consist in specified conditions under which the machine will transition between one state and another. At any given time, the Turing Machine is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition.Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
We are basically concerned about 2 types of turing machines i) deterministic ii) non-deterministic
A deterministic Turing Machine only has one transition from each state for each symbol that it is reading off the tape, in contrast a non-deterministic Turing Machine may have several such transition, i.e. it is able to check several possibilities simultaneously. It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM.When someone says P = NP , he means that one can build a deterministic TM for solving same problem in polynomial time which takes polynomial time in non-deterministic TM.So far nobody have been able to show that it can be done, but nobody has been able to prove that it cannot be done, either…lets see Vinay Deolalikar’s claim get acceptance or not !!
Also, 2 terms most programmers come across are NP-complete and NP-hard. If someone tells you that a problem is NP-complete, he basically means that it can be done in polynomial time on a non-deterministic TM, but it will take exponential time on a real computer. NP-hard ( non deterministic polynomial time hard), on the other hand, is a class of problems that are, informally, “at least as hard as the hardest problems in NP”.The precise definition here is that a problem
X is NP-hard if there is an NP-complete problem
Y such that
Y is reducible to
X in polynomial time. But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time. Confusing…right ??….don’t go into details…jus pick the essential things 😉
credits :: google