文章基本信息

标题：Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method
本地全文：下载
作者：Thore Husfeldt ; Theis Rauhe
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1997
卷号：4
期号：32
出版社：Aarhus University
摘要：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 Omega(log n/log log n). From these results we easily derive a large number of lower bounds of order Omega(log n/log log n) 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.