# Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness:

1. Is there a notion of completeness for CSL, and which languages are complete?
2. Are there natural CSL that are NP-complete?

For 2., I can certainly think of natural NP-complete languages 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.

• Let's see if I understand (2) correctly: Would it be sufficient to write a context-sensitive grammar that generates all valid 3SAT instances over a fixed alphabet of connectives and SAT variables? – Evgenij Thorstensen Oct 4 '10 at 14:47
• Well, I would not have added SAT variables as part of the alphabet (a binary encoding of their indices is good enough), but that would certainly answer my second point! – Michaël Cadilhac Oct 4 '10 at 14:53
• By the way, did you give it a try? – Michaël Cadilhac Oct 7 '10 at 12:51
• (1) As you mentioned, it is possible to write down a CSG for 3SAT, but that sounds similar to writing down a complete description of a Turing machine for the maximum-flow problem (or any specific language in P); I would not expect that it will give any insight on complexity theory. (But hey, if it turns out otherwise, I will be happy to hear it.) (2) Generally, the notion of context-sensitive grammars and the notion of NP-completeness do not go well together because the set of context-sensitive languages is not closed under polynomial-time reductions. – Tsuyoshi Ito Oct 9 '10 at 21:55
• Thanks for that comment Tsuyoshi. Indeed, a grammar for 3SAT is probably not what I'm searching for, but I went with the same reaction as yours: if it is somewhat easy/natural, I'd be interested. For your (2), one of my aim is the following: say I have a class of CS languages closed by logspace-reduction, and I want to show that my class does not (or is unlikely to) contain NP-complete problems, I would only have to show that the specific NP-complete CS language is not in my class, which could be easier if the language is naturally CS. – Michaël Cadilhac Oct 10 '10 at 3:14