¿Qué es un lenguaje "expresable" en la lógica de segundo / primer orden?

Question

Este párrafo en la página de wikipedia de la P vs NP problema, intenta explicar una caracterización de las lenguas en P y aquellos en NP, sin embargo, esta caracterización no es muy clara.

De hecho, para el primer orden de la lógica dicen que "el lenguaje de un finito, con una estructura fija de la firma, incluyendo un orden lineal relación [con un adecuado punto fijo combinador]"; pero no está claro lo que esto significa, y no parece ser explicado.

Para existencial de segundo orden de la lógica, el artículo sólo dice "NP es el conjunto de idiomas expresable existencial de segundo orden de la lógica", sin ninguna explicación: ¿qué significa para un idioma para ser expresable en (existencial) de segundo orden de la lógica ?

Así que mi pregunta es

Lo que hacen estas caracterizaciones decir, exactamente ?

Para responder, se puede asumir sé lo que es un lenguaje formal, que sé que lo primero que la lógica de orden existencial y de segundo orden de la lógica, y que yo sepa una cantidad decente de modelo de la teoría. Tenga en cuenta que no estoy pidiendo una prueba de la caracterización (aunque si hay un rápido uno no me molestaría ver), sólo para una definición de la caracterización.

Answer 1

Una palabra $w$ sobre un alfabeto finito $A$ tiene asociada una (de primer orden) estructura definida de la siguiente manera. El vocabulario tiene una relación binaria símbolo $<$ y unario relación símbolos $P_a$ para cada letra $a\in A$. La estructura asociada a $w$ tiene conjunto subyacente $\{1,2,\dots,n\}$ donde $n$ es la longitud de $w$; $<$ se interpreta como el habitual orden de los números naturales $1,2,\dots,n$; y cada una de las $P_a$ se interpreta como el conjunto de las $i\in\{1,2,\dots,n\}$ tal que el $i$-ésima carta en $w$ es $a$.

Un lenguaje de $L$ se dice que se expresa por una fórmula $\phi$ (en algunos lógica) si y sólo si $L$ es el conjunto de las palabras $w$ cuya estructura asociada satisface $\phi$.

EDIT: En el OP de la sugerencia, me voy a poner aquí el enlace (originalmente en un comentario) http://web.eecs.umich.edu/~gurevich/Ópera/152.pdf a un documento que describe los distintos fija operadores de punto y de los asociados de la lógica.