On the complexity of finding a local maximum of functions on discrete planar subsets
From MaRDI portal
Publication:1884980
DOI10.1016/S0304-3975(03)00426-2zbMath1071.68032OpenAlexW2028456923MaRDI QIDQ1884980
Publication date: 27 October 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00426-2
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Sperner's lemma and robust machines
- On the query complexity of finding a local maximum point.
- Discrete Isoperimetric Problems
- Search Problems in the Decision Tree Model
- Sequential Minimax Search for a Maximum