On the complexity of finding a local maximum of functions on discrete planar subsets

DOI10.1016/S0304-3975(03)00426-2zbMath1071.68032OpenAlexW2028456923MaRDI QIDQ1884980

Anton Mityagin

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

zbMATH Keywords

Computational complexityDecision treesLocal maximum search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Chaos and Shadowing Around a Heteroclinically Tubular Cycle With an Application to Sine‐Gordon Equation

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

This page was built for publication: On the complexity of finding a local maximum of functions on discrete planar subsets