About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1984
Conference paper
NONDETERMINISTIC VERSUS PROBABILISTIC LINEAR SEARCH ALGORITHMS.
Abstract
The 'component counting lower bound' known for deterministic linear search algorithms (LSAs) also holds for their probabilistic versions (PLSAs) for many problems, even if two-sided error is allowed, and if one does not charge for probabilistic choice. This implies lower bounds on PLSAs for, e. g. , the element distinctness problem (n log n) or the knapsack problem (n+ZZThese results yield the first separations between probabilistic and nondeterministic LSAs, because the above problems are nondeterministically much easier. Previous lower bounds for PLSAs either only worked for one-sided error on the side where the problems are hard even nondeterministically or only for probabilistic comparison trees.