Reducing Tarski to Unique Tarski (In the Black-Box Model)
Abstract
Abstract. We study the problem of finding a Tarski fixed point over the [Formula: see text]-dimensional grid [Formula: see text]. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.
Fields of Study & Subjects
History and Theory of Mathematics
Markov Chains and Monte Carlo Methods
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- SIAM Journal on Computing
- Volume
- 55
- Issue
- 1
- Pages
- 1–27
- Publication date
- 6 January 2026
- Language
- EN