## 4 Lempel-Ziv Compression on a Parallel System
### The Completeness Results  
NC is the class of problems solvable with a polynomial number of processors in polylogarithmic time on a parallel random access machine and it is conjectured to be a proper subset of P, the class of problems solvable in sequential polynomial time. LZ2 and LZW compression with an unbounded dictionary have been proved to be P-complete [6] and, therefore, hard to parallelize. SC is the class of problems solvable in polylogarithmic space and sequential polynomial time. The LZ2 algorithm with LRU deletion heuristic on a dictionary of size O\((\log^{k}n)\) can be performed in polynomial time and O\((\log^{k}n\log\log n)\) space, where \(n\) is the length of the input string. In fact, the trie requires O\((\log^{k}n)\) space by using an array implementation since the number of children for each node is bounded by the alphabet cardinality. The \(\log\log n\) factor is required to store the information needed for the LRU deletion heuristic since each node must have a different age, which is an integer value between 0 and the dictionary size. Obviously, this is true for the LZW algorithm as well. If the size of the dictionary is O\((\log^{k}n)\), the LRU strategy is log-space hard for SC\({}^{k}\), the class of problems solvable simultaneously in polynomial time and O\((\log^{k}n)\) space [7]. The problem belongs to SC\({}^{k+1}\). This hardness result is not so relevant for the space complexity analysis since \(\Omega(\log^{k}n)\) is an obvious lower bound to the work space needed for the computation. Much more interesting is what can be said about the parallel complexity analysis. In [7] it was shown that LZ2 (or LZW) compression using the LRU deletion heuristic with a dictionary of size \(c\) can be performed in parallel either in O\((\log n)\) time with \(2^{\text{O}(c\log c)}n\) processors or in \(2^{\text{O}(c\log c)}\log n\) time with O\((n)\) processors. This means that if the dictionary size is constant, the compression problem belongs to NC. NC and SC are classes that can be viewed in some sense symmetric and are believed to be incomparable. Since log-space reductions are in NC, the compression problem cannot belong to NC when the dictionary size is polylogarithmic if NC and SC are incomparable. We want to point out that the dictionary size \(c\) figures as an exponent in the parallel complexity of the problem. This is not by accident. If we believe that SC is not included in NC, then the SC\({}^{k}\)-hardness of the problem when \(c\) is O\((\log^{k}n)\) implies the exponentiation of some increasing and diverging function of \(c\). In fact, without such exponentiation either in the number of processors or in the parallel running time, the problem would be SC\({}^{k}\)-hard and in NC when \(c\) is O\((\log^{k}n)\). Observe that the P-completeness of the problem, which requires a superpolylogarithmic value for \(c\), does not suffice to infer this exponentiation since \(c\) can figure as a multiplicative factor of the time function. Moreover, this is a unique case so far where somehow we use hardness results to argue that practical algorithms of a certain kind (NC in this case) do not exist because of huge multiplicative constant factors occurring in their analysis. In [7] a relaxed version (RLRU) was introduced which turned out to be the first (and only so far) natural SC\({}^{k}\)-complete problem. RLRU partitions the dictionary in \(p\) equivalence classes, so that all the elements in each class are considered to have the same \"age\" for the LRU strategy. RLRU turns out to be as good as LRU even when \(p\) is equal to 2 [29]. Since RLRU removes an arbitrary element from the equivalence class with the \"older\" elements, the two classes (when p is equal to 2) can be implemented with a couple of stacks, which makes RLRU slightly easier to implement than LRU in addition to be more space efficient.