  For typical first-order logical theories, satisfying assignments have a
straightforward finite representation that can directly serve as a certificate
that a given assignment satisfies the given formula. For non-linear real
arithmetic with transcendental functions, however, no general finite
representation of satisfying assignments is available. Hence, in this paper, we
introduce a different form of satisfiability certificate for this theory,
formulate the satisfiability verification problem as the problem of searching
for such a certificate, and show how to perform this search in a systematic
fashion. This does not only ease the independent verification of results, but
also allows the systematic design of new, efficient search techniques.
Computational experiments document that the resulting method is able to prove
satisfiability of a substantially higher number of benchmark problems than
existing methods.
