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.