pipette
ENEnglish

The Six-Dimensional Tarski Problem is -Hard

Krist\'of Z\'olomy

Preprint

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