(Note that parsing grammatically correct English sentences is an NP hard problem.)

I feel like I've seen this claim mentioned before here on PM, although I can't find anything via super search. It's not something that I've heard about anywhere else. Do you have a source for this? A natural reduction from, say, 3-SAT to English grammaticity would be quite interesting indeed. I wonder if the subset of English grammar that is used consists of fairly standard constructions, and not obscure things that native speakers may disagree on.