普萊斯伯格算術

普萊斯伯格算術是自然數的一階理論，包含加法但沒有乘法。 因此，它不如 皮亞諾算術 強大。 然而，它很有趣，因為與 皮亞諾算術 的情況不同，存在一種演算法可以判定普萊斯伯格算術中的任何給定陳述是否為真（Presburger 1929）。 由於羅賓遜和塔斯基對 判定問題 的否定回答，對於一般算術不存在這樣的演算法。 Presburger (1929) 還證明了他的算術是一致的（不包含矛盾）和完備的（每個陳述都可以被證明或證偽），這對於 皮亞諾算術 來說是錯誤的，這是 哥德爾第一不完備性定理 的結果。

Fischer 和 Rabin (1974) 證明，每種判定普萊斯伯格語句真假的演算法的執行時間至少為 ，其中 為某個常數， 為普萊斯伯格語句的長度。 因此，這個問題是目前已知的少數幾個被證明需要超過多項式執行時間的問題之一。