In automated reasoning, we often want to know if a set of mathematical constraints has a solution. For polynomials over real numbers, this is a solved problem: Alfred Tarski proved in 1948 that the first-order theory of real closed fields is fully decidable. If your system only contains addition, multiplication, and polynomial inequalities, an automated solver can theoretically always tell you whether a solution exists.
But real-world engineering does not stop at polynomials. If you want to model the trajectory of a rocket, the behavior of an autonomous vehicle, or the loss function of a neural network, you immediately encounter transcendental functions like $\sin(x)$, $e^x$, and $\log(x)$.
As soon as a single transcendental function is introduced, Tarski's guarantees vanish. The theory becomes fundamentally undecidable. This theoretical wall creates a massive bottleneck for formal verification and automated theorem proving.
How do modern solvers bypass this undecidability barrier to reason about transcendental functions? The solution relies on two core insights: incremental linearization and $\delta$-decidability.
The Transcendental Wall
To understand why transcendental functions break standard solvers, consider how computers represent numbers and equations. Standard Satisfiability Modulo Theories (SMT) solvers excel at linear arithmetic because they can reason about precise, rational boundaries.
However, as noted by Cimatti et al., transcendental functions frequently yield irrational outputs for rational inputs. For instance, even if $x$ is a simple fraction, $e^x$ or $\sin(x)$ is almost always irrational. This makes it impossible for a standard digital computer to represent or verify exact satisfying assignments.
Furthermore, as highlighted by Matsuzaki et al., these functions escape the boundaries of Real Closed Fields entirely. Periodic functions like $\sin(x)$ can intersect with polynomials an infinite number of times, allowing one to implicitly define integers and encode Diophantine equations—rendering the logic algorithmically undecidable.
Strategy 1: Incremental Linearization
If we cannot solve transcendental equations exactly, we can approximate them. The most prominent strategy used in modern SMT solvers is incremental linearization, an abstraction-refinement loop that translates non-linear curves into a shifting set of linear constraints.
Instead of forcing the solver's core engine to understand $y = e^x$, the system initially treats $e^x$ as an uninterpreted function—essentially a black box. The solver might guess a solution where $x = 0$ and $y = 5$.
Obviously, $5 \neq e^0$. The solver has made an error because it lacks context. In response, the system computes a linear lemma to correct the solver's behavior. It calculates the tangent line to the curve $y = e^x$ at $x = 0$ (which is $y = x + 1$) and a secant line bounding a relevant interval. It then injects these linear constraints back into the solver.
y ^
| / / (True Curve: y = e^x)
5 |-------- * /
| / /
| / / <-- Tangent constraint added: y >= x + 1
1 |------* /
| / /
----+----+----> x
| 0
Now, the solver is forbidden from picking any point where $y < x + 1$. If the solver chooses another invalid point, the system generates another tangent or secant line, gradually boxing the solver into an increasingly tight linear envelope around the true transcendental curve.
As detailed by Irfan et al. and Cimatti et al., this approach works because the solver only needs to be accurate where it is actively searching, rather than computing a perfect global representation of the function.
The Challenge of Trigonometry
While functions like $e^x$ are monotonic and relatively well-behaved, trigonometric functions introduce severe complications. As Irfan et al. point out, the periodic nature of $\sin(x)$ and the presence of transcendental constants like $\pi$ make it incredibly difficult to determine precise intervals for concavity. Solvers must use highly specialized heuristics to track which quadrant the search is currently exploring to ensure that the generated tangent and secant bounds remain mathematically sound.
Despite these hurdles, combining incremental linearization with other algebraic techniques (like cylindrical algebraic coverings) has allowed modern tools like the cvc5 solver to achieve state-of-the-art performance in non-linear domains, as shown by Kremer et al..
Strategy 2: Shifting the Goalpost via $\delta$-Decidability
Incremental linearization attempts to find exact solutions by refining bounds. But what if the exact solution is fundamentally unrepresentable, causing the refinement loop to run forever?
To guarantee termination, we have to change the question we ask the solver. This is the core intuition behind $\delta$-decidability, a framework introduced by Avigad et al..
Instead of asking whether a formula is exactly satisfiable ($f(x) = 0$), a $\delta$-complete solver asks whether it is satisfiable under a tiny, user-defined numerical perturbation ($\delta$).
$$\text{Is there an } x \text{ such that } |f(x)| \le \delta ?$$
By relaxing the problem from an exact point-search to an interval-search, the problem shifts from undecidable to decidable.
Why $\delta$-Decidability Guarantees Termination
In an exact decision procedure, a solver can get trapped in an infinite game of bisection, trying to pinpoint an irrational intersection. In a $\delta$-declared framework, the solver uses interval arithmetic to bound the behavior of transcendental functions within boxes of width $\delta$, as implemented by Althoff et al..
When the solver encounters a constraint, it performs a branch-and-prune search over the domain:
- Interval Evaluation: It computes the interval bounds of the transcendental function over a given region.
- Pruning: If the interval completely misses the target zone (even when expanded by $\delta$), that entire region of the search space is safely discarded.
- Termination: Because the search space is bounded and we stop dividing once our intervals reach a width of $\delta$, the algorithm is guaranteed to terminate in a finite number of steps.
As Solar-Lezama et al. demonstrated, this framework can be extended to complex $\exists\forall$ (exists-forall) problems, allowing automated tools to handle global optimization and robust control problems that were previously entirely out of reach.
Real-World Impact
Unlocking the ability to reason about transcendental functions has fundamentally expanded the scope of formal verification.
- Cyber-Physical Systems & Differential Equations: Physical systems are governed by differential equations whose solutions are inherently transcendental. Frameworks like KeYmaera X use these advanced arithmetic foundations to verify the safety of autonomous trains and surgical robots, though they still face significant computational overhead (Platzer et al.; Gallicchio et al.).
- Continuous Planning: AI planning tools like SMTPlan+ can now compile complex continuous physics directly into SMT formulas, allowing robots to plan actions around non-linear dynamics (Cashmore et al.).
- Machine Learning Theory: Modern hyperparameter tuning and algorithm configuration frameworks rely heavily on exponentials and logarithms. By moving past purely rational models, researchers can now provide rigorous performance guarantees for modern machine learning pipelines (Balcan et al.).
By blending the flexibility of numerical approximation with the rigor of symbolic logic, the verification of transcendental functions bridges the gap between idealized mathematical theories and the messy, continuous reality of physical systems.
Key Foundational Work
Delta-Decidability over the Reals (2012) — contributed 1 concept elements to this direction.
Combining decision procedures for the reals (2006) — contributed 1 concept elements to this direction.