On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
Dominik Kempa, Tomasz Kociumaka
原文摘要
We study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms that take $O(n\sqrt{\log n})$ time for instances described in $Θ(n)$ machine words ($Θ(n\log n)$ bits). This complexity class, one of six hardness levels identified by Chan and Pătraşcu [SODA 2010], includes problems from several domains: Counting Inversions, string processing problems (BWT Construction, LZ77 Factorization, Longest Common Substring, Batched Longest Previous Factor Queries, Batched Inverse Suffix Array Queries), and computational geometry tasks (Orthogonal Range Counting, Orthogonal Segment Intersection Counting). We offer two main contributions: We establish new links between the above string problems and Dictionary Matching, a classic task solvable using the Aho-Corasick automaton. We restrict Dictionary Matching to instances with $Θ(n)$ binary patterns of length $m = Θ(\log n)$ each, and we prove that, unless these instances can be solved in $o(n\sqrt{\log n})$ time, the aforementioned string problems cannot be solved faster either. Via further reductions, we extend this hardness to Counting Inversions (a fundamental component in geometric algorithms) and thus to Orthogonal Range Counting and Orthogonal Segment Intersection Counting. This hinges on String Nesting, a new problem which is equivalent to Dictionary Matching and can be reduced to Counting Inversions in three steps. Together, our results unveil a single problem, with two equivalent formulations, that underlies the hardness of nearly all major problems currently occupying the $O(n\sqrt{\log n})$ level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. As an auxiliary outcome of our framework, we also prove that several central string problems can be efficiently reduced to their versions over the binary alphabet.
cs.DS