I'm interested in two questions regarding <a href="http://en.wikipedia.org/wiki/Context-sensitive_language">context-sensitive languages</a> (CSL) and completeness: <ol> <li> Is there a notion of completeness for CSL, and which languages are complete?</li> <li> Are there natural CSL that are NP-complete?</li> </ol> For 2., I can certainly think of natural NP-complete that are CSL (as CSL is equal to NSPACE[$n$], SAT is a CSL), but I'm searching for the other way around, i.e., a context-sensitive grammar describing an NP-complete language.