Demystifying P != NP and Recent News around it

There has been buzz in math and computational groups after Vinay Deolalikar's proof that P != NP was made public. Here i will try to explain the basic concepts, and some analysis of his proof based on my discussion with experts (from university) and some from blogs in this area.

Algorithm
Means some set of computing instructions, like finding shortest number in the set of numbers.

P
P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input. Note the length of problem and time are synonymously used here on. If there are N elements, O(N) is the order and complexity of the problem/solution. Polynomial time means in the order of N raise to power of 2, 3 ...integer. The theory behind this comes from Turing Machine by Alan Turing.

NP
NP, meanwhile, stands for "non-deterministic polynomial time" and refers to a set of problems whose solutions are hard to find, but easy to verify.
Simple Example to explain
if someone tells you that the combination to their suitcase with 3 keys is 9-1-1, then you can just dial up 9-1-1 and see if it opens. The important thing is that it's easy to verify whether you've got the right answer, but it's not necessarily easy, or even feasible, to come up with the right answer in the first place. So, an example of an NP problem is, "find the combination to this suitcase." If you come up with a way to answer that question, it's easy for me to tell whether you're right. It would require permutation which is 10*10*10 trials, easier to do for this the example but the point is important, that out of 1000 trials one will match, while verification was easy 1 step.All NP problem needs is Prover (to prove) and Verifier to verify in polynomial time. Also problems in decision area (giving true/false) rather than outputs (search) are focussed on.

NP-Hard
NP-Hard problems are one that follow Cook's Theorem as necessary-sufficient property,i.e. if we can say that the problem can be solved efficiently (polynomial time) then we can solve any problem in NP-Hard domain. First problem identified was logic problem of boolean satisfiability. Reducing various problems to other well known problems we can show that, it is NP-Hard. Example, Graph clique problem can be reduced to boolean satisfiability problem and hence its in NP-Hard using Cook's theorem.

NP-Complete
The set of NP problems (the majority of NP problems, in fact) that could be solved by adapting a single, easy solution, if an easy solution were possible. NP-Completeness for any problem requires only 2 things
1. Proof that it is NP (Prover-Verifier in poly time)
2. Its NP-Hard using Reduction technique (like above).

Whether P = NP or P != NP ?
this has been the fundamental problem that Mathamaticians have been trying to prove. Clay Institute has Million dollar reward for such proof.

If P = NP, then problems that appear hard to solve (as the one above) actually have very easy solutions. Deolalikar says he has proven that P != NP -- as many mathematicians have believed -- meaning problems do exist that are easier to verify than to solve.

Is this the only Proof?
He is not the only one giving this proof about P and NP, as you can see just in 2010 there has been few people giving proofs and many others in past
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Proof Analysis
Here is an intresting discussion on this which i have been tracking by the expert Neil Immerman in Finite State Models.

http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

A comment by Albert Atserias gives a very high-level description of the proof strategy and points to what seems to "go wrong" (see also the surrounding comments).
He says: Deolalikar aims to show that
(1) the solution spaces of all problems in P have a simple structure; and
(2) the solution space of random k-SAT does not have this simple structure. In approaching (1),
Deolalikar seems to have misapplied the tools he uses from finite model theory -- a certain key reduction does not seem to preserve a "simplicity" property.

Masala Fish in Banana Leaf

Ingredients:

1. 1Kg , 2 Pound Fish (2-3 Pomfret, 2-3 Mackerel are ideal). Small size fish would be good in this preparation
2. 1-1.5 cup grated coconut
3. 2-3 Red chilies (based on spice level)
4. 2-5 green chillies (based on spice level)
5. 1 tablespoon(s) coriander seeds
6. 2 teaspoon(s) cumin seeds
7. 2 tablespoon(s) chopped garlic
8. few fenugreek seeds
9. 2 tablespoon(s) lemon juice
10. 1 cup chopped coriander leaves

Methodology:

1. Clean the fish, make horizontal slits which are not deep, and one side way slit from the gill area till tail going side-by-side for putting masala inside. Make sure you don't cut the fish in to 2 halves.
2. Put some salt, lemon juice and keep it for 30-45 minutes.
3. Fry 2 to 8 for about 2 minutes and then grind it to fine paste with 10 and 1 table spoon lemon with little water, paste has to be thick.
4. Apply the masala to inside the fish and outside.
5. Place the masala applied fish on the banana leaf. Carefully tie fish with thread so that it stays intact.
6. Now there are 2 ways to proceed. a) can steam the fish with banana leaf in idli or any steamer, b) shallow fry for 1-2 minutes and bake it in oven for few minutes.

You can sprinkle little fresh lemon or give "tadka" of curry-leaves and green chillies for further spicying this.