Carnegie Mellon University
Browse

δ-Decidability over the Reals

Download (230.14 kB)
journal contribution
posted on 2012-04-01, 00:00 authored by Sicun Gao, Jeremy AvigadJeremy Avigad, Edmund M Clarke

Given any collection F of computable functions over the reals, we show that there exists an algorithm that, given any sentence A containing only bounded quantifiers and functions in F, and any positive rational number delta, decides either “A is true”, or “a delta-strengthening of A is false”. Moreover, if F can be computed in complexity class C, then under mild assumptions, this “delta-decision problem” for bounded Sigma k-sentences resides in Sigma k(C). The results stand in sharp contrast to the well-known undecidability of the general first-order theories with these functions, and serve as a theoretical basis for the use of numerical methods in decision procedures for formulas over the reals.

History

Publisher Statement

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Date

2012-04-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC