diff options
| -rw-r--r-- | mgr.tex | 3 |
1 files changed, 2 insertions, 1 deletions
@@ -1300,7 +1300,8 @@ problem has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. We do not know whether this is an optimal solution. If the question answering step's complexity could be reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth -would then be known to be in \lineardelaylin. Or is there a lower bound on +would then be known to be solvable in +\qptime{$O_{\varphi}(n)$}{$O_{\varphi}(m)$}. Or is there a lower bound on computing LCA closures in this setting, for example, would it be possible to reduce comparison sorting to computing LCA closures? |