论文标题
用于查找Tarski固定点的更快的算法
A faster algorithm for finding Tarski fixed points
论文作者
论文摘要
Dang等人。给出了一种算法，可以使用$ o（\ log^{k} n）$ QUERIES在$ k $二维晶格中找到tarski固定点。多个作者猜想该算法是最佳的[dang等，Etessami等]，实际上，这已被证明是二维实例[Etessami等]。我们表明，通过给出三维tarski问题的$ O（\ log^2 n）$ QUERY算法，这些猜想在三个或更高的维度上是错误的。我们还为$ k $二维的tarski问题提供了一个新的分解定理，该问题与我们的三维算法结合使用，给出了$ o（\ log^{2 \ lceil k/3 \ rceil} n）$ k $ - dimensional问题。
Dang et al. have given an algorithm that can find a Tarski fixed point in a $k$-dimensional lattice of width $n$ using $O(\log^{k} n)$ queries. Multiple authors have conjectured that this algorithm is optimal [Dang et al., Etessami et al.], and indeed this has been proven for two-dimensional instances [Etessami et al.]. We show that these conjectures are false in dimension three or higher by giving an $O(\log^2 n)$ query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for $k$-dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an $O(\log^{2 \lceil k/3 \rceil} n)$ query algorithm for the $k$-dimensional problem.
