Have you ever heard of caching? In theory, if the binary code hasn't changed, then if the NaCl module is cached properly, you'd only have to download it the first time. Of course, you'd have to redownload it anytime it changes on the server, but look at it this way - you get instant access to updates.
And if you read the article, Google's purpose in this is not to create huge, full applications in native code and then run them through the browser, but combine this native calculations with the cloud. In Photoshop, that might mean your computer's GPU handles all the image processing, but all the data to save and export to different formats is sent to the cloud for processing. Or, Google Docs' spreadsheets could offload all the cell formula calculations in native code, rather than sending a request back to the server. The point of this native code is to speed up lots of little actions, not build entire applications.
Nope, and that's why NP-complete problems are currently not calculable (at least not in the true, best case scenario, unless you get really lucky and your algorithm succeeds on an early attempt). The concept of a nondeterministic Turing machine is basically that you have a machine that as it goes along to solve the problem, can instantaneously split itself into multiple copies to try to calculate different paths along the algorithm.
If it helps, picture it like a hypothetical infinite core processor. Every time the algorithm hits a branch (if, switch, that kind of idea), rather than simply choose one of them to follow, it creates a copy of itself on another core and each copy starts going through one of the paths. On our limited and finite machines, this gets impossibly large very quickly (think lots of recursion). So if they really did prove P=NP, that's a major leap for Computer Science. But it's still hard to believe, seeing how many other people have spent so long trying.
Um...you can keep 'compressing' things in whatever algorithm (gzip, zip, rar, mp3, whatever), but eventually it won't make the file any smaller at all. All compression does is replace repeated sequences with a key to replace it and strip those duplicates out. As soon as the file lacks that sequenciality, there is no more stuff that can be simplified. And even if you could, the processor power to continuous decompress it out of all those recursive compressions would kill the battery life of any smartphone.
In short, you could NOT replicate what Google search does on hundreds of dedicated servers, with only a cell phone and an SD card.
System going down in 5 minutes.