Hardness Results for Dynamic Problems by Extensions of Fredman and Saks'
Chronogram Method
Thore Husfeldt November 1997 |
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
Available as PostScript, PDF, DVI. |