P NP

Well I have always been consufed with NP, P CO-NP and all such funda.... so today decided to get the basic funda clear about this:

NP: It is the class of problems that can be solved by non deterministic finite automata by making a polynomial number of guesses and the solution can be verified in polynomial time.

P: is a set of problems that can be solved in an polynomial time thus concluding that if a problem is P then it is NP

now the question comes that whether NP=P.... the answer to this is uncertain as P is the class of problems that can be solved "easily" in polynomial time while NP is a class of problems that can be varified in a polynomial time and hence they are considered to be different.

NP - complete: a problem is said to be NP - Complete if it is NP and every other NP problem can be reduced to it in polynomial time.... now its significance is that to show how hard a particular problem is: i.e. we can prove that for a particular problem no polynomial time algorithm exsists by contradiction if we reduce a problem for which no polynomial time solution exsists to it in polynomial time.... and finally if for any NP complete problem we find a polynomial time algorithm then since all the NP problems are reducible to it, all of them will have a polynomial time solution and hence NP class will now become equivalent to P and thus existance of NP complete problems is a factor which makes people believe that NP != P....

finally if a problem is not NP but all the NP problems are reducible to it in polynomial time then it is known as NP- hard.... which implies that a NP hard problem is atleast as hard as any other NP problem, infact it might be harder.