A lower bound on complexity of a locator cellular automaton solution for the closest neighbor search problem

DOI10.3103/s0027132223050078zbMath1530.68187OpenAlexW4389943079MaRDI QIDQ6155012

D. I. Vasilev, El'yar E. Gasanov

Publication date: 16 February 2024

Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0027132223050078

zbMATH Keywords

cellular automatahomogeneous structuresclosest neighbor search problem

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item