Post History
#2: Post edited
by
clemens
·
2026-02-18T18:52:19Z (7 months ago)
changed the summary to be somewhat clearer
- Transform your statement
- \[\text{If a language is not an $X$, then it must have space/time complexity $\omega(f)$ (or $\Omega(f)$)}\]
- into its contrapositive:
- \[\text{If a language has complexity $O(g), g < f$, then it is an X}\]
- Now perhaps it is easier to see why this problem tends to be very hard: *every* computational problem can be treated as a sort of "language". For instance [$s$-$t$ connectivity](https://en.wikipedia.org/wiki/STCON) can be thought of as a language in which graphs with two connected points are valid expressions and graphs with two disconnected points are invalid expressions. And this example suffices to show that even languages with space complexity $O(\log n)$ can be quite nontrivial.
- Indeed, the only natural way (that I see) of solving such a problem is by making some universal "translation algorithm" from $O(g)$ languages to $X$ languages. I think the regex example you gave illustrates the difficulty with this approach well: it's easy to show that a regex needs only constant space complexity, but as soon as you add almost anything (say, backreferences) regexes become either pushdown automata or Turing-complete. (Of course, pushdown automata all have linear complexity, but not conversely---something with linear complexity would correspond to a "double-pushdown automaton" but I'm not sure if there's a conventional name for languages parsable by such automata!)
It is not easy, within the framework of formal language theory, to "fill the gap" in between, say, a pushdown automaton and a Turing machine in an especially elegant way.
- Transform your statement
- \[\text{If a language is not an $X$, then it must have space/time complexity $\omega(f)$ (or $\Omega(f)$)}\]
- into its contrapositive:
- \[\text{If a language has complexity $O(g), g < f$, then it is an X}\]
- Now perhaps it is easier to see why this problem tends to be very hard: *every* computational problem can be treated as a sort of "language". For instance [$s$-$t$ connectivity](https://en.wikipedia.org/wiki/STCON) can be thought of as a language in which graphs with two connected points are valid expressions and graphs with two disconnected points are invalid expressions. And this example suffices to show that even languages with space complexity $O(\log n)$ can be quite nontrivial.
- Indeed, the only natural way (that I see) of solving such a problem is by making some universal "translation algorithm" from $O(g)$ languages to $X$ languages. I think the regex example you gave illustrates the difficulty with this approach well: it's easy to show that a regex needs only constant space complexity, but as soon as you add almost anything (say, backreferences) regexes become either pushdown automata or Turing-complete. (Of course, pushdown automata all have linear complexity, but not conversely---something with linear complexity would correspond to a "double-pushdown automaton" but I'm not sure if there's a conventional name for languages parsable by such automata!)
- In short, I think it is precisely because of the versatility of, say, $O(n \log n)$ deterministic algorithms or $O(\log n)$ nondeterministic algorithms that it is very hard to correlate them *precisely* with natural concepts in formal grammar such as context-free or deterministic context-free languages, even though as you noted it tends to be possible to *upper-bound* space/time complexity given grammatical complexity.
#1: Initial revision
by
clemens
·
2026-02-18T18:46:52Z (7 months ago)
Transform your statement
\[\text{If a language is not an $X$, then it must have space/time complexity $\omega(f)$ (or $\Omega(f)$)}\]
into its contrapositive:
\[\text{If a language has complexity $O(g), g < f$, then it is an X}\]
Now perhaps it is easier to see why this problem tends to be very hard: *every* computational problem can be treated as a sort of "language". For instance [$s$-$t$ connectivity](https://en.wikipedia.org/wiki/STCON) can be thought of as a language in which graphs with two connected points are valid expressions and graphs with two disconnected points are invalid expressions. And this example suffices to show that even languages with space complexity $O(\log n)$ can be quite nontrivial.
Indeed, the only natural way (that I see) of solving such a problem is by making some universal "translation algorithm" from $O(g)$ languages to $X$ languages. I think the regex example you gave illustrates the difficulty with this approach well: it's easy to show that a regex needs only constant space complexity, but as soon as you add almost anything (say, backreferences) regexes become either pushdown automata or Turing-complete. (Of course, pushdown automata all have linear complexity, but not conversely---something with linear complexity would correspond to a "double-pushdown automaton" but I'm not sure if there's a conventional name for languages parsable by such automata!)
It is not easy, within the framework of formal language theory, to "fill the gap" in between, say, a pushdown automaton and a Turing machine in an especially elegant way.