On the query complexity of finding a local maximum point
Publication date
2000-11
Authors
Rastsvelaev, A.L.
Beklemishev, L.D.
Editors
Advisors
Supervisors
DOI
Document Type
Preprint
Metadata
Show full item recordCollections
License
Abstract
We calculate the minimal number of queries sufficient to find a local
maximum point of a functiun on a discrete interval for a model with M parallel queries, M≥1. Matching upper and lower bounds are obtained.
The bounds are formulated in terms of certain Fibonacci type sequences
of numbers.
Keywords
computational complexity, decision trees, local maximum, Fibonacci numbers