Aritmética de Presburger
De Wikipedia, a enciclopédia encyclopedia
A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma. Tem esse nome em honra de Mojżesz Presburger, o qual a apresentou em 1929. A assinatura da aritmética de Presburguer contém apenas a operação de adição e equalização, suprimindo a operação de multiplicação totalmente. Isso inclui o esquema de indução.
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Dezembro de 2011) |
A Aritmética de Presburger é muito mais fraca do que a aritmética de Peano, que inclui tanto a operação de adição quanto a de multiplicação. Ao contrário da aritmética de Peano, a aritmética de Presburger é uma teoria decidível. Isto significa que é possível efetivamente determinar, por qualquer sentença na linguagem da aritmética Presburger, se essa frase é dedutível dos axiomas da aritmética de Presburger. O tempo de funcionamento assintótico complexidade computacional deste problema de decisão é duplamente exponencial, como mostrado por Fischer e Rabin (1974).