|
Presburger arithmetic is an interesting example in complexity theory and computation because Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has at least a runtime of 2^(2^(cn)) for some constant c. Here, n is the length of the Presburger statement. Hence, the problem is one of the few that provably need more than polynomial run time. |
|
Presburger arithmetic is an interesting example in complexity theory and computation because Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has at least a runtime of 2^(2^(cn)) for some constant c. Here, n is the length of the Presburger statement. Hence, the problem is one of the few that provably need more than polynomial run time. |
|
:∀ x ∀ y : ( (&exists; z : x + z = y + 1) ⇒ (∀ z : ¬ (((1 + y) + 1) + z = x) ) ) |
|
:∀ x ∀ y : ( (∃ z : x + z = y + 1) ⇒ (∀ z : ¬ (((1 + y) + 1) + z = x) ) ) |
|
/Talk? |
![[Home]](wikipedia.png)