Papex

Open problem · Mathematics · Open

Tarski’s exponential function problem

Is there an algorithm that decides every first-order statement about the real numbers with addition, multiplication and the exponential function?

Summary

Tarski showed that the theory of the reals with addition and multiplication is decidable. With the exponential function added, Macintyre and Wilkie proved decidability assuming a real version of Schanuel’s conjecture; the unconditional question is open.

Why it is open

A decision method for a class of statements is, in Tarski's words, a method "by means of which, given any sentence θ, one can always decide in a finite number of steps" whether θ belongs to the class [1]. In a report for the RAND Corporation, dated 1948 and revised in 1951, Tarski gave such a method for the true sentences of elementary algebra: first-order statements about real numbers built from addition, multiplication, order, the logical connectives and quantifiers over real numbers [1].

He then asked what happens when new functions are added [1]. With a predicate for the integers, or a periodic function such as the sine, there is no decision method, because the integers become definable and, by what he calls the Gödel–Church–Rosser result, their arithmetic has none [1]. The same holds for exponentiation of complex numbers, since the complex exponential function is periodic [1]. For the real exponential function, or an exponential with a fixed base such as 2, Tarski wrote that "the decision problem is open", that it "is of a great theoretical and practical interest", and that its difficulties "arise from the fact that our knowledge of conditions for the solvability of equations and inequalities in the enlarged system is far from adequate" [1].

No body sets a bar for a resolution: it would be a decision method proved correct without unproved hypotheses, or a proof that none exists. Since 1996 the question has been tied to number theory: Angus Macintyre and Alex Wilkie proved decidability assuming a real form of Schanuel's conjecture, and showed that decidability is equivalent to a weaker conjecture of their own [3, 4, 9]. On 16 October 2026 the Wikipedia list on which this page's status rests still included the problem [10].

What is known

Real closed fields (1948–1951). Tarski's method decides every sentence of elementary algebra, and of elementary geometry through coordinates [1]. In modern terms, the theory of the real field admits quantifier elimination, so every formula is equivalent to one without quantifiers, and it is axiomatised by the axioms of real closed ordered fields [9].

Model completeness and o-minimality (1994–1996). With the exponential function added, quantifier elimination fails, by a counterexample of William Osgood [9]. Wilkie proved instead that the theory is model complete: every formula is equivalent to an existential one, so every definable set is a projection of the zero set of an exponential polynomial p(x1, …, xn, e^x1, …, e^xn) [3, 9]. Combined with Askold Khovanskii's theorem that such zero sets have finitely many connected components, this makes the real exponential field o-minimal: every definable subset of the line is a finite union of intervals [2, 9]. Wilkie also proved model completeness for the reals with restricted Pfaffian functions, which covers the exponential function restricted to the closed interval from 0 to 1 [3]. Lou van den Dries, Macintyre and David Marker proved quantifier elimination for the reals with exponentiation and all restricted analytic functions, which also gives o-minimality [2].

Decidability under Schanuel's conjecture (1996). The real form of Schanuel's conjecture says that if real numbers a1, …, an are linearly independent over the rationals, then a1, …, an, e^a1, …, e^an have transcendence degree at least n over the rationals [9]. The transcendence degree of a list of numbers is the largest number of them that together satisfy no non-zero polynomial equation with rational coefficients. Macintyre and Wilkie showed that, if it holds, there is an algorithm to test whether an exponential polynomial with rational coefficients has a real zero, and that such an algorithm implies decidability [4, 9]. They also showed that decidability is equivalent to a weak form of Schanuel's conjecture [9]. In the form given by Gallego-Hernández and Mansutti, the theory is decidable as soon as there is a procedure that, given exponential polynomials f1, …, fn and g with integer coefficients, returns a positive integer t such that at every non-singular common real zero α of f1, …, fn, either g(α) = 0 or |g(α)| > 1/t [8]. Khovanskii's theorem guarantees that such a t exists; the open part is computing it [8]. The conditional result has since been used "as a black-box" to obtain conditional decidability results on dynamical systems, automata, neural-network verification, stochastic games and differential privacy [8]. A p-adic version of Schanuel's conjecture likewise implies decidability for the p-adic integers with exponentiation, and it appears in work on the Skolem problem [7] (see the Papex page Skolem problem).

Unconditional fragments and variants (2008–2026). Melanie Achatz, Scott McCallum and Volker Weispfenning gave a decision procedure for prenex sentences in which only the outermost quantified variable occurs inside the exponential function, implemented in the Redlog system [5]. McCallum and Weispfenning extended the method to other transcendental functions, including the natural logarithm and the inverse tangent [6]. Jorge Gallego-Hernández and Alessio Mansutti call this "a non-trivial fragment" that is "unconditionally decidable", and note that "No complexity bound is known" [8]. Their own work, the extended version of a 2025 conference paper posted as a preprint, decides the existential theory of the reals with a predicate for the integer powers of a fixed computable number known to be algebraic or transcendental, and removes the appeal to Schanuel's conjecture from an earlier decidability result for the entropic risk threshold problem on stochastic games [8]. A 2026 preprint by Alessandro Berarducci and Francesco Gallinaro, not peer reviewed, proves, assuming the real Schanuel conjecture, that the theory is axiomatised by the axioms of definably complete exponential fields with exp′ = exp, which gives a new proof of the Macintyre–Wilkie result [9]. Without that assumption, it proves model completeness of similar axioms for the exponential function restricted to the interval (−1, 1) [9].

Main approaches

Through Schanuel's conjecture. Prove the real form of Schanuel's conjecture, which would make the Macintyre–Wilkie algorithm unconditional [4, 9]. Strongest evidence: the Macintyre–Wilkie theorem shows that the real form suffices [4, 9]. Main difficulty: Schanuel's conjecture is itself listed as unsolved [10].

Effective bounds. Prove the weak form of Schanuel's conjecture directly, by computing the bound t [8, 9]. Strongest evidence: Khovanskii's theorem gives the existence of t, and decidability is equivalent to computing it [8, 9]. Main difficulty: Gallego-Hernández and Mansutti write that "the crux of the problem concerns how to effectively compute such a number" [8].

Explicit axioms. A complete theory is decidable if and only if it is recursively axiomatised, so it suffices to find explicit axioms and prove them complete [9]. Strongest evidence: the Berarducci–Gallinaro axiomatisation, complete under Schanuel's conjecture, and their unconditional model completeness result for the restricted exponential function [9]. Main difficulty: the authors use Schanuel's conjecture to ensure that every model of their restricted theory has an archimedean submodel, one without infinitely large elements, and an unconditional proof that this theory is polynomially bounded, meaning that every definable function of one variable is eventually bounded by a polynomial, "remains an open problem" [9].

Decidable fragments. Decide restricted classes of sentences, or variants with predicates for integer powers [5, 6, 8]. Strongest evidence: the procedures of Achatz, McCallum and Weispfenning, and the complexity bounds of Gallego-Hernández and Mansutti [5, 6, 8]. Main difficulty: each covers a fragment only, and for the first no complexity bound is known [8].

Open sub-questions

  1. Polynomial boundedness. Is the theory of definably complete restricted exponential fields, which Berarducci and Gallinaro prove model complete, polynomially bounded without assuming Schanuel's conjecture [9]?
  2. More variables in the exponential. Can the decision procedure of Achatz, McCallum and Weispfenning be extended to sentences in which two quantified variables occur inside the exponential function [5, 6]?
  3. Complexity of the known fragment. What is the computational complexity of deciding the fragment of Achatz, McCallum and Weispfenning, for which no bound is known [8]?
  4. Weaker hypotheses. Berarducci and Gallinaro note that, under the weak form of Schanuel's conjecture, their theories become complete once its axiom scheme is added. Is the theory of definably complete exponential fields with exp′ = exp complete under that weak form alone [9]?
  5. Removing the conjecture elsewhere. Which conditional decidability results that use the Macintyre–Wilkie theorem as a black box can be made unconditional by reduction to decidable fragments, as was done for the entropic risk threshold problem [8]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Tarski, A. (1951). A Decision Method for Elementary Algebra and Geometry, 2nd edition, prepared for publication with the assistance of J. C. C. McKinsey. RAND Corporation report R-109 (1 August 1948, revised May 1951); also published by University of California Press, 1951. Source · Checked 16 Oct 2026
  2. van den Dries, L., Macintyre, A. & Marker, D. (1994). The elementary theory of restricted analytic fields with exponentiation. Annals of Mathematics 140(1), 183–205. 10.2307/2118545 · Checked 16 Oct 2026
  3. Wilkie, A. J. (1996). Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. Journal of the American Mathematical Society 9(4), 1051–1094. 10.1090/s0894-0347-96-00216-0 · Checked 16 Oct 2026
  4. Macintyre, A. & Wilkie, A. J. (1996). On the decidability of the real exponential field. In P. Odifreddi (ed.), Kreiseliana: About and Around Georg Kreisel, 441–467. A K Peters. Source · Checked 16 Oct 2026
  5. Achatz, M., McCallum, S. & Weispfenning, V. (2008). Deciding polynomial-exponential problems. In Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation (ISSAC '08), 215–222. 10.1145/1390768.1390799 · Checked 16 Oct 2026
  6. McCallum, S. & Weispfenning, V. (2012). Deciding polynomial-transcendental problems. Journal of Symbolic Computation 47(1), 16–31. 10.1016/j.jsc.2011.08.004 · Checked 16 Oct 2026
  7. Bilu, Y., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D. & Worrell, J. (2022). Skolem meets Schanuel. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics 241, 20:1–20:15. 10.4230/LIPIcs.MFCS.2022.20 · Checked 16 Oct 2026
  8. Gallego-Hernández, J. & Mansutti, A. (2026). On the existential theory of the reals enriched with integer powers of a computable number. Preprint, arXiv:2502.02220 (version 4, 31 August 2026), extended version of a STACS 2025 paper, submitted to Logical Methods in Computer Science, not peer reviewed in this form. Source · Checked 16 Oct 2026
  9. Berarducci, A. & Gallinaro, F. (2026). On the elementary theory of the real exponential field. Preprint, arXiv:2603.08365 (version 3, 25 September 2026), not peer reviewed. Source · Checked 16 Oct 2026
  10. Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics