m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/mgr.tex
diff options
context:
space:
mode:
Diffstat (limited to 'mgr.tex')
-rw-r--r--mgr.tex3
1 files changed, 2 insertions, 1 deletions
diff --git a/mgr.tex b/mgr.tex
index 4e21ad6..9e4c530 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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?