Timeline for grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2014 at 23:00 | comment | added | Yuval Filmus | A satisfying assignment of length $k$ takes $k$ bits to store, and you can evaluate the formula in linear space in the formula size, so you can enumerate over all satisfying assignments and evaluate the formula on all of them in linear space. | |
| Apr 4, 2014 at 22:10 | comment | added | symplectomorphic | Thanks. Can you give me a rough sense of why the propositional algorithm will be linearly bounded? If $k$ is the length of the formula, then $2^k$ is a (weak) upper bound on the number of truth assignments. But I'm very bad at seeing how much space would be needed. Why is it linear? | |
| Apr 4, 2014 at 21:39 | history | answered | Yuval Filmus | CC BY-SA 3.0 |