9

It is known that Presburger arithmetic is decidable, but algorithms for solving the decision problem for it can take very long (over double exponential time in statement length). The fact that the algorithms can take so long suggests that there are "hard" problems Presburger arithmetic can encode, but of course the fact that things are decidable suggests things can't be too hard.

Are there well known open problems that can be phrased in Presburger arithmetic? Or at least any problems that are natural enough (I'm worried that types of statement we know are hard here are very contrived) that a human might care about them, and hard to solve? I'm not seriously acquainted with this area, so please forgive me if the terminology I used is incorrect.

Beren Gunsolus
  • 2,616
  • Consider that the Presburg arithmetic is very weak. It cannot even formalize the concept of a prime number. Of course , there must be very hard problems within reach of the Presburg arithmetic, but I doubt we know in advance which of those very hard problems are of this kind. – Peter Oct 16 '20 at 13:51
  • If we could formalize Collatz with this theory, we would know it must be decidable , but I do not think this works since it probably would have been done already. – Peter Oct 16 '20 at 13:52
  • 2
    Maybe this is relevant: https://gilkalai.wordpress.com/2019/03/22/danny-nguyen-and-igor-pak-presburger-arithmetic-problem-solved/ It has 2 examples of NP-hard problems in PA, and allows extensions that ascend the polynomial hierarchy. It, however, probably does not really count as an open problem by your criteria of naturalness. – twnly Oct 16 '20 at 15:10

0 Answers0