Talk:Presburger arithmetic
|
|
- 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.
You mean more than polynomial or more than exponential ? --Taw
Both. But "polynomial time" P is a pretty important class of problems, and this is one of the few problems that can be shown not to be in there, so that's why I explicitly mentioned polynomial time. --AxelBoldt
I know just a little of mathematics but I don't see clearly the meaning of the last theorem... ? x ? y : ( (? z : x + z = y + 1) ? (? z : ¬ (((1 + y) + 1) + z = x) ) ) May be the last part of it is " = z + x " instead of " + z = x ". --jimmer_lactic
- Working from the inside out of (∀ z : ¬ (((1 + y) + 1) + z = x) ):
- ((1 + y) + 1) means y+2;
- (((1 + y) + 1) + z = x) means that z (a non-negative integer) can be added to y+2 to make x;
- (∀ z : ¬ (((1 + y) + 1) + z = x) ) means that for any non-negative integer, it cannot be added to y+2 to make x, so y+2 must be strictly greater than x. --Henrygb 23:28, 31 Jan 2005 (UTC)
"and in fact completeness for it is false; this is the content of Gödel's incompleteness theorem." : I don't think this is quite true. The latter
theorem states only that the axioms of Peano arithmetic are either inconsistent
or incomplete. It would be nice if we knew that the axioms were consistent
(and therefore that arithmetic was incomplete), but there is still a possibility
of inconsistency. Disclaimer: I am not a logician. -Mike