The Six-Dimensional Tarski Problem is -Hard
En palabras de los autores
We study the deterministic query complexity of finding a fixed point of a monotone function , where querying returns . For fixed , earlier work established a lower bound of and an upper bound of for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to . In particular, we obtain the optimal deterministic query complexity in six dimensions.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 17 pages, 7 figures