From e701e6d72c9f6c793b5df5d5a5d044473d4e9b13 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 7 Dec 2022 18:00:11 +0100 Subject: Change complexity class notation --- mgr.tex | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) 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? -- cgit v1.2.3