Proving P!=NP: "...Ryan has taken the first real baby step in decades."
blog.computationalcomplexity.org
blog.computationalcomplexity.org
The question is why are complexity theorists excited about this.
When a problem is too hard to solve, you look for easier versions to solve first. Here the easier version is to prove that the complexity class NEXP (which is intuitively vastly more powerful than even NP) is bigger than a certain class of circuits of constant depth (circuits with polynomial depth are known to be roughly equivalent to P, and constant-depth circuits are intuitively vastly less powerful).
ETA: the circuits considered here are "non-uniform," which makes the previous paragraph slightly inaccurate. Nevertheless, the point stands that the goal here is to separate two complexity classes that are intuitively very different in their power.
Circuit lower bounds -- proving that a restricted class of circuits, as above, is in fact limited in its computational power -- have been notorious for their hardness. The reason one would want to prove this kind of statement is not because these circuits are objects of practical interest, but because of the proof techniques that would come out as a side-effect, in the hope that these techniques would be applicable in solving other, harder problems.
So that's the gist of it: the 3 reasons this theorem is exciting are: proof techniques, proof techniques and proof techniques.
Now some of the statements from the post should hopefully make a lot more sense:
This approach converts weak algorithms for solving circuit satisfiability questions into circuit lower bounds. Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways.
Ryan breaks through the natural proofs barrier in an interesting way. ... he avoids the issue by using diagonalization and so his proof does not fulfill the constructivity requirement of natural proofs.
What's going on here is that there are often meta-proofs in complexity theory showing that a certain approach to proofs won't work. The "natural proofs barrier" being referred to is (apparently) a limit on what you can achieve by a certain type of "natural" construction that is explained in this post by Lipton: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu...
The one thing I haven't touched upon is why there are "mod m" gates in the circuit class under consideration. That is also (surprise, surprise) related to proof techniques. As Luca Trevisan explains, using mod m gates instead of binary gates or mod-prime gates disables two well-known classes of proofs ("fixing variables to random values" and "low-degree polynomial approximation"), ensuring that some heavy artillery will need to be developed in order to prove statements about them. http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower...
http://scottaaronson.com/blog/?p=472
In essence he has shown that a certain class of problem that have been thought to be difficult, are difficult, in the sense that circuits (or calculations) required to solve them have a minimum size requirement. The comments in that post are just as useful as the announcements, if not more so.
I suspect I can't explain further - my understanding is inexpert anyway, and I stick to explaining the absolute basics to let people at least have a launching point:
There's a lesson here kids: when you can't prove something, "diagonilization" is the proof-tool of choice. Sure, if you include it, you won't have proven anything either, or useful, or correct, but you might just get a PhD.
(For those who are curious: diagonilization is a proof that takes the form: "Imagine you did this impossible thing. With the result of doing that impossible thing, now try and do this other, reasonable thing. You can't! So whatever properties I can derive from not being able to do this other, reasonable thing are true. (Please ignore that the first step is impossible, and focus on my brilliance in discussing the second, reasonable step.)"
That is, in a nutshell, the diagonilization "proof". The rest of the details are just there to make it look like it's actually logic or math. Best not to look too closely.
Also, you'll be shocked, SHOCKED to learn that not a single result in the real world relies on the diagonilization proof (though a lot of real-world PhDs would no doubt be affected by it's loss). sigh Mathematicians are idiots when they try and do logic. Stick with numbers, boys.