Timeline for Completeness and Context-Sensitive Languages.
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2017 at 1:58 | history | tweeted | twitter.com/StackCSTheory/status/838931809756921856 | ||
| Jan 15, 2011 at 12:57 | history | edited | Hermann Gruber |
edited tags
|
|
| Nov 28, 2010 at 13:41 | vote | accept | Michaël Cadilhac | ||
| Nov 25, 2010 at 22:28 | answer | added | Hermann Gruber | timeline score: 9 | |
| Oct 10, 2010 at 3:14 | comment | added | Michaël Cadilhac | 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. | |
| Oct 9, 2010 at 21:55 | comment | added | Tsuyoshi Ito | (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. | |
| Oct 7, 2010 at 12:52 | history | edited | Michaël Cadilhac | CC BY-SA 2.5 |
added 2 characters in body
|
| Oct 7, 2010 at 12:51 | comment | added | Michaël Cadilhac | By the way, did you give it a try? | |
| Oct 4, 2010 at 14:53 | comment | added | Michaël Cadilhac | 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! | |
| Oct 4, 2010 at 14:47 | comment | added | Evgenij Thorstensen | 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? | |
| Oct 3, 2010 at 23:25 | history | edited | Michaël Cadilhac | CC BY-SA 2.5 |
added 10 characters in body
|
| Oct 3, 2010 at 22:44 | history | asked | Michaël Cadilhac | CC BY-SA 2.5 |