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.