Do yourself a favor and take the time to read this paper not just to learn about P=?NP but also to see a model of how technical writing ought to be done. Scott Aaronson is truly the Richard Feynman of our day. Not only is he freaking brilliant, but his writing style is accessible, not too mathy, even humorous at times. This made me LOL:
"We see a similar “invisible fence” phenomenon in Leslie Valiant’s program of “accidental algorithms” [246]. The latter are polynomial-time algorithms, often for planar graph problems, that exist for certain parameter values but not for others, for reasons that are utterly opaque if one doesn’t understand the strange cancellations that the algorithms exploit. A prototypical result is the following:
[Abstruse theorem elided, but it boils down to: there's this weird problem with a parameter k that can be proven to have polynomial-time solutions for some values of k and proven to be NP-hard for other values of k.]
Needless to say (because otherwise you would’ve heard!), in not one of these examples have the “P region” and the “NP-complete region” of parameter space been discovered to overlap."
> to see a model of how technical writing ought to be done
Well, this is semi-popular technical writing directed at people who are not theory-of-computation researchers. If all scientific writing would be written like this, then all papers would be at least hundreds of pages long and skip important details.
It's absolutely wonderful -- and I think vital -- that a researcher takes the time to do popular writing, but most scientific writing can't be popular. This kind of writing is usually reserved for surveys, like this one. Popular renderings of groundbreaking research also exist in publications like Scientific American, and blog posts by researchers like Aaronson who like (and are good at) communicating their findings in this way, but the important details are often very much research-level and quite impenetrable to all but very specialized researchers.
>Well, this is semi-popular technical writing directed at people who are not theory-of-computation researchers.
Nothing wrong about directing a technical writing to people other than "theory-of-computation" researchers. Most people are not theory-of-computation researchers, not just laymen, but also also statistics researchers, topology researchers, geometricians, logicians, etc.
>If all scientific writing would be written like this, then all papers would be at least hundreds of pages long and skip important details.
GP obviously means all scientific writing aimed at the same kind of audience.
Theory-of-computation researchers would obviously not need such a volume at all in the first place: they already know this stuff, and they can just directly read pure research on P vs NP, not some summary of what P vs NP means.
That said, all scientific writing (including those aimed/produced by experts in a field) could take from the quality of the wording, and the attention to clarity. It doesn't mean it has to also follow the lengthy introduction to its subject.
In other words, it seems to me like we're splitting hairs, while the intended meaning was pretty clear from the GP's comment context.
Actually I'm pretty sure many theoretical computer scientists find this useful too; it covers at a high level recent approaches for proving P != NP, such as Ryan Williams' approach, the GCT approach, etc.
Scott himself said that he had to do a lot of legwork to understand GCT. I can bet that this is the case for most theoreticians.
Complexity theory is a vast field; it's difficult to become acquainted with the disparate portions of the field. Surveys such as this are valuable for the field.
It's a survey that's been made more popular than the usual. Not all surveys can be like this or they'd all be at least this long. Even relatively long surveys are usually restricted to about half the length of this one.
"We see a similar “invisible fence” phenomenon in Leslie Valiant’s program of “accidental algorithms” [246]. The latter are polynomial-time algorithms, often for planar graph problems, that exist for certain parameter values but not for others, for reasons that are utterly opaque if one doesn’t understand the strange cancellations that the algorithms exploit. A prototypical result is the following:
[Abstruse theorem elided, but it boils down to: there's this weird problem with a parameter k that can be proven to have polynomial-time solutions for some values of k and proven to be NP-hard for other values of k.]
Needless to say (because otherwise you would’ve heard!), in not one of these examples have the “P region” and the “NP-complete region” of parameter space been discovered to overlap."