Aritmética presburger

La aritmética de Presburger es la teoría de primer orden de los números naturales con suma, nombrada en honor a Mojżesz Presburger, quien la introdujo en 1929. La firma de la aritmética de Presburger contiene solo la operación de suma y la igualdad., omitiendo por completo la operación de multiplicación. Los axiomas incluyen un esquema de inducción.

La aritmética de Presburger es mucho más débil que la aritmética de Peano, que incluye operaciones de suma y multiplicación. A diferencia de la aritmética de Peano, la aritmética de Presburger es una teoría decidible. Esto significa que es posible determinar algorítmicamente, para cualquier oración en el lenguaje de la aritmética de Presburger, si esa oración es demostrable a partir de los axiomas de la aritmética de Presburger. Sin embargo, la complejidad computacional asintótica en tiempo de ejecución de este algoritmo es al menos doblemente exponencial, como muestran Fischer & Rabín (1974).

Resumen

El lenguaje de la aritmética de Presburger contiene constantes 0 y 1 y una función binaria +, interpretada como suma.

En este lenguaje, los axiomas de la aritmética de Presburger son los cierres universales de lo siguiente:

1. ¬(0 = x + 1)
2. x + 1 = Sí. + 1 → x = Sí.
3. x + 0 = x
4. x +Sí. + 1) =x + Sí.) + 1
5. Vamos P()x) ser una fórmula de primer orden en el idioma de Presburger aritmética con una variable libre x (y posiblemente otras variables libres). Entonces la siguiente fórmula es un axioma:
   ()P(0) ∧x()P()x) → P()x + 1)) →Sí. P()Sí.).

(5) es un esquema de axioma de inducción, que representa un número infinito de axiomas. Estos no pueden ser reemplazados por ningún número finito de axiomas, es decir, la aritmética de Presburger no es finitamente axiomatizable en lógica de primer orden.

La aritmética de Presburger puede verse como una teoría de primer orden con igualdad que contiene precisamente todas las consecuencias de los axiomas anteriores. Alternativamente, se puede definir como el conjunto de oraciones que son verdaderas en la interpretación pretendida: la estructura de números enteros no negativos con constantes 0, 1 y la suma de números enteros no negativos.

La aritmética de Presburger está diseñada para ser completa y decidible. Por lo tanto, no puede formalizar conceptos como divisibilidad o primalidad, o, más generalmente, cualquier concepto de número que lleve a la multiplicación de variables. Sin embargo, puede formular instancias individuales de divisibilidad; por ejemplo, prueba "para todo x, existe y: (y + y = x) ∨ (y + y + 1 = x)". Esto establece que cada número es par o impar.

Propiedades

Mojżesz Presburger demostró que la aritmética de Presburger es:

• consistente: No hay ninguna declaración en Presburger aritmética que puede ser deducido de los axiomas de tal manera que su negación también puede ser deducido.
• completo: Para cada declaración en el idioma de Presburger aritmética, ya sea es posible deducirla de los axiomas o es posible deducir su negación.
• decidable: Existe un algoritmo que decide si cualquier declaración dada en Presburger arithmetic es un teorema o un no teorema.

La decidibilidad de la aritmética de Presburger se puede demostrar mediante la eliminación de cuantificadores, complementada con un razonamiento sobre la congruencia aritmética. Los pasos utilizados para justificar un algoritmo de eliminación de cuantificadores se pueden utilizar para definir axiomatizaciones recursivas que no necesariamente contienen el esquema axiomático de inducción.

Por el contrario, la aritmética de Peano, que es la aritmética de Presburger aumentada con la multiplicación, no es decidible, como consecuencia de la respuesta negativa al Entscheidungsproblem. Por el teorema de incompletitud de Gödel, la aritmética de Peano es incompleta y su consistencia no es demostrable internamente (pero vea la prueba de consistencia de Gentzen).

Complejidad computacional

El problema de decisión para Presburger arithmetic es un ejemplo interesante en la teoría de la complejidad computacional y la computación. Vamos n ser la longitud de una declaración en Presburger aritmética. Entonces Fischer & Rabin (1974) demostró que, en el peor de los casos, la prueba de la declaración en la lógica de primer orden tiene longitud al menos ${displaystyle 2^{2^{cn}}$, para alguna constante cPor lo tanto, su algoritmo de decisión para Presburger arithmetic tiene tiempo de ejecución al menos exponencial. Fischer y Rabin también probaron que para cualquier axiomatización razonable (definida precisamente en su papel), existen teoremas de longitud n que tienen dobles pruebas de longitud exponenciales. Intuitivamente, esto sugiere que hay límites computacionales en lo que puede ser probado por los programas informáticos. El trabajo de Fischer y Rabin también implica que Presburger arithmetic se puede utilizar para definir fórmulas que calculan correctamente cualquier algoritmo mientras las entradas sean menos que límites relativamente grandes. Los límites pueden aumentarse, pero solo usando nuevas fórmulas. Por otro lado, una parte superior triplicada exponencial en un procedimiento de decisión para Presburger Arithmetic fue probada por Oppen (1978).

Berman (1980) mostró un límite de complejidad más estrecho utilizando clases de complejidad alterna. El conjunto de sentencias verdaderas en la aritmética de Presburger (PA) se muestra completo para TimeAlternations(2^2nO(1), n). Así, su complejidad está entre el tiempo no determinista doble exponencial (2-NEXP) y el espacio doble exponencial (2-EXPSPACE). La completitud está bajo reducciones de muchos a uno de tiempo polinomial. (Además, tenga en cuenta que, si bien la aritmética de Presburger se abrevia comúnmente PA, en matemáticas en general, PA generalmente significa aritmética de Peano).

Para obtener un resultado más detallado, sea PA(i) el conjunto de enunciados PA verdaderos Σ_i, y PA(i, j) el conjunto de enunciados verdaderos Σ_{i< /sub> Sentencias PA con cada bloque cuantificador limitado a j variables. '<' se considera libre de cuantificadores; aquí, los cuantificadores acotados se cuentan como cuantificadores.
PA(1, j) está en P, mientras que PA(1) es NP-completo.
Para yo > 0 yj > 2, PA(i + 1, j) es ΣiP-completo. El resultado de dureza solo necesita j>2 (a diferencia de j=1) en el último bloque cuantificador.
Para i>0, PA(i+1) es ΣiEXP-completa (y es TimeAlternations(2^nO(i), i)-completa).}

Corto ${displaystyle Sigma _{n}$ Presburger Arithmetic${displaystyle n confiado2}$) es ${displaystyle Sigma ¿Qué?$ completo (y por lo tanto NP completo para ${displaystyle n=3}$). Aquí, 'short' requiere atado (es decir,. ${displaystyle O(1)}$) tamaño de la frase excepto que las constantes enteros están sin límites (pero su número de bits en conteos binarios contra el tamaño de entrada). También, ${displaystyle Sigma _{2}}$ dos PA variable (sin la restricción de ser 'short') es NP-completo. Corto ${displaystyle Pi _{2}$ (y así ${displaystyle Sigma _{2}}$) PA está en P, y esto se extiende a la programación lineal de enteros paramétricos de dimensión fija.

Aplicaciones

Debido a que la aritmética de Presburger es decidible, existen probadores de teoremas automáticos para la aritmética de Presburger. Por ejemplo, el sistema asistente de prueba Coq presenta la táctica omega para la aritmética de Presburger y el asistente de prueba Isabelle contiene un procedimiento de eliminación de cuantificador verificado por Nipkow (2010). La doble complejidad exponencial de la teoría hace inviable el uso de probadores de teoremas en fórmulas complicadas, pero este comportamiento ocurre solo en presencia de cuantificadores anidados: Nelson & Oppen (1978) describe un probador automático de teoremas que utiliza el algoritmo simplex en una aritmética de Presburger extendida sin cuantificadores anidados para probar algunos de los casos de fórmulas aritméticas de Presburger sin cuantificadores. Los solucionadores de teorías de módulo de satisfacibilidad más recientes utilizan técnicas de programación de enteros completos para manejar fragmentos sin cuantificadores de la teoría aritmética de Presburger.

La aritmética de Presburger se puede ampliar para incluir la multiplicación por constantes, ya que la multiplicación es una suma repetida. La mayoría de los cálculos de subíndices de matrices caen dentro de la región de los problemas decidibles. Este enfoque es la base de al menos cinco sistemas de prueba de corrección para programas informáticos, comenzando con el Stanford Pascal Verifier a fines de la década de 1970 y continuando hasta el sistema Spec# de Microsoft de 2005.

Relación entera definible por Presburger

Ahora se dan algunas propiedades sobre las relaciones de enteros definibles en Presburger Arithmetic. En aras de la simplicidad, todas las relaciones consideradas en esta sección son sobre números enteros no negativos.

Una relación es definible por Presburger si y solo si es un conjunto semilineal.

Una relación integer única ${displaystyle R.$, es decir, un conjunto de enteros no negativos, es Presburger-definible si y sólo si es en última instancia periódica. Es decir, si existe un umbral ${displaystyle tin mathbb {N}$ y un período positivo ${displaystyle pin mathbb {N}$ tal que, para todo entero ${displaystyle n}$ tales que ${displaystyle Silencioso para siempregeq t}$, ${displaystyle nin R}$ si ${displaystyle n+pin R}$.

Por el teorema de Cobham-Semenov, una relación es presburger-definible si y sólo si es definible en Büchi aritmética de la base ${displaystyle k}$ para todos ${displaystyle kgeq 2}$. Una relación definible en Büchi aritmética de base ${displaystyle k}$ y ${displaystyle k'}$ para ${displaystyle k}$ y ${displaystyle k'}$ ser números enteros multiplicativamente independientes es Presburger definible.

Una relación entero ${displaystyle R.$ es Presburger-definible si y sólo si todos los conjuntos de enteros que son definibles en primera orden lógica con adición y ${displaystyle R.$ (es decir, Presburger Arithmetic más un predicado para ${displaystyle R.$) son Presburger-definible. Equivalentemente, para cada relación ${displaystyle R.$ que no es presburger-definible, existe una fórmula de primer orden con adición y ${displaystyle R.$ que define un conjunto de enteros que no es definible utilizando solamente adición.

Caracterización de Muchnik

Las relaciones definibles por Presburger admiten otra caracterización: por el teorema de Muchnik. Es más complicado de enunciar, pero condujo a la prueba de las dos caracterizaciones anteriores. Antes de que se pueda enunciar el teorema de Muchnik, se deben introducir algunas definiciones adicionales.

Vamos ${displaystyle Rsubseteq mathbb {N} }$ ser un conjunto, la sección ${displaystyle x_{i}=j}$ de ${displaystyle R.$, para ${displaystyle i realizadas}$ y ${displaystyle jin mathbb {N}$ se define como

${displaystyle left{(x_{0},ldotsx_{i-1},x_{i+1},ldotsx_{d-1})in mathbb {N} ^{d-1}mid (x_{0},ldotsx_{i-1},j,x_{i+1},ldotsx_{d-1})in Rright}$

Dados dos sets ${displaystyle R,Ssubseteq mathbb {N} }$ y a ${displaystyle d}$-tuple de enteros ${displaystyle (p_{0},ldotsp_{d-1}in mathbb {N} ^{d}$, el conjunto ${displaystyle R.$ se llama ${displaystyle (p_{0},dotsp_{d-1}$-peródico en ${displaystyle S.$ si, para todos ${displaystyle (x_{0},dotsx_{d-1}in S}$ tales que ${displaystyle (x_{0}+p_{0},dotsx_{d-1}+p_{d-1})in S,}$ entonces ${displaystyle (x_{0},ldotsx_{d-1}in R}$ si ${displaystyle (x_{0}+p_{0},dotsx_{d-1}+p_{d-1})in R}$. Para ${displaystyle sin mathbb {N}$, el conjunto ${displaystyle R.$ se dice que ${displaystyle s}$-peródico dentro ${displaystyle S.$ si es ${displaystyle (p_{0},ldotsp_{d-1}}$-peródico para algunos ${displaystyle (p_{0},dotsp_{d-1}in mathbb {Z} ^{d}$ tales que

${displaystyle sum _{i=0}{d-1}Sobrevivir_{i}$

Por último, ${displaystyle k,x_{0},dotsx_{d-1}in mathbb {N}$ Deja

${displaystyle C(k,(x_{0},ldotsx_{d-1})=left{(x_{0}+c_{0},dotsx_{d-1}+c_{d-1})mid 0leq ¿Qué?$

denota el cubo del tamaño ${displaystyle k}$ cuya esquina menor es ${displaystyle (x_{0},dotsx_{d-1}}$.

Intuitivamente, el entero ${displaystyle s}$ representa la longitud de un cambio, el entero ${displaystyle k}$ es el tamaño de los cubos y ${displaystyle t}$ es el umbral antes de la periodicidad. Este resultado sigue siendo cierto cuando la condición

${displaystyle sum _{i=0}{d-1}x_{i}]$

es reemplazado por ${displaystyle min(x_{0},ldotsx_{d-1}]$ o por ${displaystyle max(x_{0},ldotsx_{d-1}]$.

Esta caracterización llevó al llamado " criterio definible para la definabilidad en la aritmética Presburger", es decir: existe una fórmula de primer orden con adición y una ${displaystyle d}$- predicar ${displaystyle R.$ que sostiene si ${displaystyle R.$ es interpretado por una relación definible de Presburger. El teorema de Muchnik también permite probar que es decidable si una secuencia automática acepta un conjunto definible Presburger.