Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Presburger arithmetic
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== Computational complexity === The decision problem for Presburger arithmetic is an interesting example in [[computational complexity theory]] and [[computation]]. Let ''n'' be the length of a statement in Presburger arithmetic. Then {{harvtxt|Fischer|Rabin|1974}} proved that, in the worst case, the proof of the statement in first-order logic has length at least <math>2^{2^{cn}}</math>, for some constant ''c''>0. Hence, their decision algorithm for Presburger arithmetic has runtime at least exponential. Fischer and Rabin also proved that for any reasonable axiomatization (defined precisely in their paper), there exist theorems of length ''n'' that have [[double exponential function|doubly exponential]] length proofs. Fischer and Rabin's work also implies that Presburger arithmetic can be used to define formulas that correctly calculate any algorithm as long as the inputs are less than relatively large bounds. The bounds can be increased, but only by using new formulas. On the other hand, a triply exponential upper bound on a decision procedure for Presburger arithmetic was proved by {{harvtxt|Oppen|1978}}. A more tight complexity bound was shown using alternating complexity classes by {{harvtxt|Berman|1980}}. The set of true statements in Presburger arithmetic (PA) is shown complete for [[Alternating Turing machine|TimeAlternations]](2<sup>2<sup>n<sup>O(1)</sup></sup></sup>, n). Thus, its complexity is between double exponential nondeterministic time (2-NEXP) and double exponential space (2-EXPSPACE). Completeness is under [[Karp reduction]]s. (Also, note that while Presburger arithmetic is commonly abbreviated PA, in mathematics in general PA usually means [[Peano arithmetic]].) For a more fine-grained result, let PA(i) be the set of true Ξ£<sub>i</sub> PA statements, and PA(i, j) the set of true Ξ£<sub>i</sub> PA statements with each quantifier block limited to j variables. '<' is considered to be quantifier-free; here, bounded quantifiers are counted as quantifiers.<br/> PA(1, j) is in P, while PA(1) is NP-complete.{{sfn|Nguyen Luu|2018|loc=chapter 3}}<br/> For i > 0 and j > 2, PA(i + 1, j) is [[Polynomial_hierarchy|Ξ£<sub>i</sub><sup>P</sup>-complete]]. The hardness result only needs j>2 (as opposed to j=1) in the last quantifier block.<br/> For i>0, PA(i+1) is [[Exponential_hierarchy|Ξ£<sub>i</sub><sup>EXP</sup>-complete]].{{sfn|Haase|2014|pp=47:1-47:10}} Short <math>\Sigma_n</math> Presburger Arithmetic (<math>n>2</math>) is <math>\Sigma_{n-2}^P</math> complete (and thus NP complete for <math>n=3</math>). Here, 'short' requires bounded (i.e. <math>O(1)</math>) sentence size except that integer constants are unbounded (but their number of bits in binary counts against input size). Also, <math>\Sigma_2</math> two variable PA (without the restriction of being 'short') is NP-complete.{{sfn|Nguyen|Pak|2017}} Short <math>\Pi_2</math> (and thus <math>\Sigma_2</math>) PA is in P, and this extends to fixed-dimensional parametric integer linear programming.{{sfn|Eisenbrand|Shmonin|2008}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)