Abstract:
We introduce new models for dynamic computation based on the
cell probe model of Fredman and Yao. We give these models access to
nondeterministic queries or the right answer ± 1 as an oracle. We prove
that for the dynamic partial sum problem, these new powers do not help, the
problem retains its lower bound of 
.
From
these results we easily derive a large number of lower bounds of order
for conventional dynamic models like the random
access machine. We prove lower bounds for dynamic algorithms for reachability
in directed graphs, planarity testing, planar point location, incremental
parsing, fundamental data structure problems like maintaining the majority of
the prefixes of a string of bits and range queries. We characterise the
complexity of maintaining the value of any symmetric function on the prefixes
of a bit string
Available as PostScript, PDF, DVI.