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.

Puzzle

You are given an array with n elements { x1, x2 ... xk ... xn }. You are also given an array location k. Using constant space and O(n) time, rotate the array such that it contains { xk, xk+1 ... xn, x1, x2 ... xk-1 }.

Well the first thoughts which came to my mind were those involving swapping the elements and one can also achieve the solution this way, but its not the best way. The best way out is as follows:

We know that reversing of a list can be done in constant time. Thus do as follows:
1.reverse the list from x1 to xk-1 {xk-1, xk-2, ....., x1, xk, ...... , xn}
2.reverse the list from xk to xn {xk-1, xk-2, ....., x1, xn, ......., xk}
3.reverse the whole list {xk, xk+1, ..... xn, x1, x2, ......., xk-1}

Nice na!!!!