Time-Space Tradeoffs for Set Operations

This paper considers time-space tradeoffs for various set operations. Denoting the time requirement of an algorithm by $T$ and its space requirement by $S$, it is shown that $TS=\ohm{n^2}$ for set complementation and $TS=\ohm{n^{3/2}}$ for set intersection, in the $R$-way branching program model. In the more restricted model of comparison branching programs, the \paper\ provides two additional types of results. A tradeoff of $TS=\ohm{n^{2-\epsilon(n)}}$, derived from Yao's lower bound for element distinctness, is shown for set disjointness, set union and set intersection (where $\epsilon(n)=\bigo{(\log n)^{-1/2}}$). A bound of $TS=\ohm{n^{3/2}}$ is shown for deciding set equality and set inclusion. Finally, a classification of set operations is presented, and it is shown that all problems of a large naturally arising class are as hard as the problems bounded in this paper.

Click here for journal version.