Complexity of Presburger Arithmetic with Fixed Quantifier Dimension.

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
Read Online Read More Add to Saved list
  • Author(s): Schöning, U.
  • Source:
    Theory of Computing Systems. 1997, Vol. 30 Issue 4, p423. 6p.
  • Additional Information
    • Subject Terms:
      COMPUTATIONAL complexity; STATISTICAL decision making
    • Abstract:
      It is shown that the decision problem for formulas in Presburger arithmetic with quantifier prefix [∃[sub 1]∀[sub 2] ··· ∃[sub m]∀³] (for m odd) and [∃[sub 1]∀[sub 2] ··· ∀[sub m] ∃³ ] (for m even) is complete for the class Σ[sup P, sub m] of the polynomial-time hierarchy. Furthermore, the prefix type [∃∀∃∃] is complete for Σ[sup P, sub 2], and the prefix type [∃∀] is complete for NP. This improves results (and solves a problem left open) by Grädel [7]. [ABSTRACT FROM AUTHOR]
    • Abstract:
      Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)