Espectro de una oración

En lógica matemática , el espectro de una oración es el conjunto de números naturales que se presentan como el tamaño de un modelo finito en el que una oración dada es verdadera. Por un resultado en complejidad descriptiva , un conjunto de números naturales es un espectro si y solo si puede reconocerse en tiempo exponencial no determinista .

Definición

Sea ψ una oración de lógica de primer orden . El espectro de ψ es el conjunto de números naturales n tales que existe un modelo finito para ψ con n elementos.

Si el vocabulario de ψ consiste únicamente en símbolos relacionales, entonces ψ puede considerarse como una oración en lógica existencial de segundo orden (ESOL) cuantificada sobre las relaciones, sobre el vocabulario vacío. Un espectro generalizado es el conjunto de modelos de una oración ESOL general.

Ejemplos

• El espectro de la fórmula de primer orden

${\displaystyle \exists z,o~\forall a,b,c~\exists d,e}$

${\displaystyle a+z=a=z+a~\land ~a\cdot z=z=z\cdot a~\land ~a+d=z}$

${\displaystyle \land ~a+b=b+a~\land ~a\cdot (b+c)=a\cdot b+a\cdot c~\land ~(a+b)+c=a+(b+c)}$

${\displaystyle \land ~a\cdot o=a=o\cdot a~\land ~a\cdot e=o~\land ~(a\cdot b)\cdot c=a\cdot (b\cdot c)}$

es , el conjunto de potencias de un número primo . En efecto, con para y para , esta oración describe el conjunto de campos ; la cardinalidad de un campo finito es la potencia de un número primo. ${\displaystyle \{p^{n}\mid p{\text{ prime}},n\in \mathbb {N} \}}$ ${\displaystyle z}$ ${\displaystyle 0}$ ${\displaystyle o}$ ${\displaystyle 1}$

• El espectro de la fórmula de la lógica monádica de segundo orden es el conjunto de los números pares . En efecto, es una biyección entre y , y y son una partición del universo. Por lo tanto, la cardinalidad del universo es par. ${\displaystyle \exists S,T~\forall x~\left\{x\in S\iff x\not \in T\land ~f(f(x))=x\land ~x\in S\iff f(x)\in T\right\}}$ ${\displaystyle f}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$
• El conjunto de conjuntos finitos y co-finitos es el conjunto de espectros de la lógica de primer orden con la relación sucesora.
• El conjunto de conjuntos en última instancia periódicos es el conjunto de espectros de la lógica monádica de segundo orden con una función unaria. También es el conjunto de espectros de la lógica monádica de segundo orden con la función sucesora.

Complejidad descriptiva

El teorema de Fagin es un resultado de la teoría de la complejidad descriptiva que establece que el conjunto de todas las propiedades expresables en la lógica existencial de segundo orden es precisamente la clase de complejidad NP . Es notable ya que es una caracterización de la clase NP que no invoca un modelo de computación como una máquina de Turing . El teorema fue demostrado por Ronald Fagin en 1974 (estrictamente, en 1973 en su tesis doctoral).

Como corolario, Jones y Selman demostraron que un conjunto es un espectro si y sólo si está en la clase de complejidad NEXP . ^[1]

Una dirección de la prueba es mostrar que, para cada fórmula de primer orden , el problema de determinar si existe un modelo de la fórmula de cardinalidad n es equivalente al problema de satisfacer una fórmula de tamaño polinomial en n , que está en NP(n) y por lo tanto en NEXP de la entrada al problema (el número n en forma binaria, que es una cadena de tamaño log( n )). ${\displaystyle \varphi }$

Esto se hace reemplazando cada cuantificador existencial por una disyunción sobre todos los elementos del modelo y reemplazando cada cuantificador universal por una conjunción sobre todos los elementos del modelo. Ahora cada predicado está sobre elementos del modelo y, finalmente, cada aparición de un predicado sobre elementos específicos se reemplaza por una nueva variable proposicional. Las igualdades se reemplazan por sus valores de verdad de acuerdo con sus asignaciones. ${\displaystyle \varphi }$

Por ejemplo:

${\displaystyle \forall {x}\forall {y}\left(P(x)\wedge P(y)\right)\rightarrow (x=y)}$

Para un modelo de cardinalidad 2 (es decir, n = 2) se reemplaza por

${\displaystyle {\big (}\left(P(a_{1})\wedge P(a_{1})\right)\rightarrow (a_{1}=a_{1}){\big )}\wedge {\big (}\left(P(a_{1})\wedge P(a_{2})\right)\rightarrow (a_{1}=a_{2}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{1})\right)\rightarrow (a_{2}=a_{1}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{2})\right)\rightarrow (a_{2}=a_{2}){\big )}}$

Que luego se reemplaza por ${\displaystyle {\big (}\left(p_{1}\wedge p_{1}\right)\rightarrow \top {\big )}\wedge {\big (}\left(p_{1}\wedge p_{2}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{1}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{2}\right)\rightarrow \top {\big )}}$

donde es verdad, es falsedad y , son variables proposicionales. En este caso particular, la última fórmula es equivalente a , que es satisfacible. ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle \neg (p_{1}\wedge p_{2})}$

La otra dirección de la prueba es mostrar que, para cada conjunto de cadenas binarias aceptadas por una máquina de Turing no determinista que funciona en tiempo exponencial ( para una longitud de entrada x), existe una fórmula de primer orden tal que el conjunto de números representados por estas cadenas binarias es el espectro de . ${\displaystyle 2^{cx}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

Jones y Selman mencionan que el espectro de fórmulas de primer orden sin igualdad es simplemente el conjunto de todos los números naturales no menores que una cardinalidad mínima.

Otras propiedades

El conjunto de espectros de una teoría está cerrado bajo unión , intersección , adición y multiplicación. En general, no se sabe si el conjunto de espectros de una teoría está cerrado por complementación; este es el llamado problema de Asser. Por el resultado de Jones y Selman, es equivalente al problema de si NEXPTIME = co-NEXPTIME; es decir, si NEXPTIME está cerrado bajo complementación. ^[2]

Véase también

• Espectro de una teoría

Referencias

1. Jones, Neil D.; Selman, Alan L. (1974). "Máquinas de Turing y los espectros de fórmulas de primer orden". J. Symb. Log . 39 (1): 139–150. doi :10.2307/2272354. JSTOR  2272354. Zbl  0288.02021.
2. Szwast, Wiesław (1990). "Sobre el problema del generador". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 36 (1): 23–27. doi :10.1002/malq.19900360105. SEÑOR  1030536.

• Fagin, Ronald (1974). "Espectros generalizados de primer orden y conjuntos reconocibles en tiempo polinomial" (PDF) . En Karp, Richard M. (ed.). Complejidad de la computación . Proc. Syp. App. Math. Actas SIAM-AMS. Vol. 7. págs. 27–41. Zbl  0303.68035.
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en informática teórica. Una serie EATCS. ​​Berlín: Springer-Verlag . doi :10.1007/3-540-68804-8. ISBN. 978-3-540-00428-8.Zbl 1133.03001  .
• Immerman, Neil (1999). Complejidad descriptiva . Textos de posgrado en informática. Nueva York: Springer-Verlag. pp. 113–119. ISBN. 0-387-98600-6.Zbl 0918.68031  .
• Durand, Arnaud; Jones, Neil; Markowsky, Johann; More, Malika (2012). "Cincuenta años del problema del espectro: estudio y nuevos resultados". Boletín de lógica simbólica . 18 (4): 505–553. arXiv : 0907.5495 . Código Bibliográfico :2009arXiv0907.5495D. doi :10.2178/bsl.1804020. S2CID  9507429.