From 97ce60ab4d2d2017f4a936b71937d87ae1cb064f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 25 Apr 2022 19:53:33 +0200 Subject: [PATCH] Fixed a tiny error in decision tree lemma --- opt.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/opt.tex b/opt.tex index 202e52b..d71f983 100644 --- a/opt.tex +++ b/opt.tex @@ -882,12 +882,12 @@ than $n^4$ possible comparisons and less than $2^{n^2}$ spanning trees of~$G$, so the number of candidate decision trees is bounded by $(n^4+2^{n^2})^{2^{2n^2+1}} \le 2^{(n^2+1)\cdot 2^{2n^2+1}} \le 2^{2^{2n^2+2}} \le 2^{2^{3n^2}}$. -We will enumerate the trees in an~arbitrary order, test each of them for correctness and +We enumerate the trees in an~arbitrary order, test each tree for correctness and find the shallowest tree among those correct. Testing can be accomplished by running through all possible permutations of edges, each time calculating the MSF using any of the known algorithms and comparing it with the result given by the decision tree. The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$ -and each one can be checked in time $\O(\poly(n))$. +for sufficiently large~$n$ and each one can be checked in time $\O(\poly(n))$. On the Pointer Machine, trees and permutations can be certainly enumerated in time $\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore -- 2.39.2