Open AccessThe Bit Probe Complexity Measure Revisited
Author(s) -
Peter Bro Miltersen
Publication year - 1992
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v21i396.6631
Subject(s) - measure (data warehouse) , time complexity , mathematics , polynomial , upper and lower bounds , conjecture , complexity class , data structure , computer science , space (punctuation) , computational complexity theory , linear space , discrete mathematics , constant (computer programming) , theoretical computer science , algorithm , mathematical analysis , database , programming language , operating system
The bit probe complexity of a static data structure problem within a given size bound was defined by Elias and Flower. It is the number of bits one needs to probe in the data structure for worst case data and query with an optimal encoding of the data within the space bound. We make some furtber investigations into the properties of the bit probe complexity measure. We determine the complexity of the full problem, which is the problem where every possible query is allowed, within an additive constant. We show a trade off-between structure size and the number of bit probes for all problems. We show that the complexity of almost every problem, even with small query sets, equals that of the full problem. We show how communication complexity can be used to give small, but occasionally tight lower bounds for natural functions. We define the class of access feasible static structure problems and conjecture that not every polynomial time computable problem is access feasible. We show a link to dynamic problems by showing that if polynomial time computable functions without feasible static structures exist, then there are problems in P which can not be reevaluated efficiently on-line.