¿Existe una restricción natural de la lógica VO que captura P o NP?

El papel

• Lauri Hella y José María Turull-Torres, Cálculo de consultas con lógicas de orden superior , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009

propone lógica VO, lógica de orden variable. Esto permite la cuantificación sobre los pedidos sobre las variables. VO es bastante poderoso y puede expresar algunas consultas no computables. (Como señala Arthur Milchior a continuación, en realidad captura la totalidad de la jerarquía analítica ). Los autores muestran que el fragmento de VO obtenido al permitir solo la cuantificación universal limitada sobre las variables de orden expresa exactamente todas las consultas de ce. VO permite que las variables de orden se extiendan sobre los números naturales, por lo que limitar las variables de orden es claramente una condición natural para imponer.

¿Hay un fragmento (agradable) de VO que capture P o NP?

Como analogía, en la lógica clásica de primer orden que permite la cuantificación sobre conjuntos de objetos se obtiene una lógica más poderosa llamada lógica de segundo orden o SO. SO captura la totalidad de la jerarquía polinómica ; esto generalmente se escribe como PH = SO. Existen formas restringidas de SO que capturan importantes clases de complejidad: NP = SO, P = SO-Horn y NL = SO-Krom. Estos se obtienen al imponer restricciones a la sintaxis de las fórmulas permitidas.$\exists$

Por lo tanto, hay formas directas de restringir SO para obtener clases interesantes. Me gustaría saber si existen restricciones directas similares de VO que son aproximadamente el nivel correcto de expresividad para P o NP. Si no se conocen tales restricciones, me interesarían sugerencias para posibles candidatos, o algunos argumentos de por qué es poco probable que existan.

Revisé los (pocos) documentos que citan este, y verifiqué las frases obvias en Google y Scholar, pero no encontré nada obviamente relevante. La mayoría de los documentos que tratan sobre lógicas más poderosas que las de primer orden no parecen tratar con restricciones para reducir el poder al ámbito de los cálculos "razonables", pero parecen contentarse con morar en el universo ce de las clases aritméticas y analíticas. Estaría feliz con un puntero o una frase no obvia para buscar; esto podría ser bien conocido por alguien que trabaja en lógicas de orden superior.

Nota: Esto realmente no responde la pregunta, son solo algunos comentarios publicados como respuesta. :)

$\exists$$PH$$P$$NP$

¿Es la presencia de un cuantificador ilimitado suficiente para capturar conjuntos ce?

El problema es que probablemente desee que el lenguaje no tenga símbolos adicionales como igualdad, suma, multiplicación (¿verdad?), Si los tuviéramos entonces por el teorema MRDP, fórmulas de diofantina (cuantificadores existenciales de primer orden frente a una igualdad de dos polinomios) capturaría conjuntos ce. Si no permitimos estos símbolos en el lenguaje, el problema es más complicado, se pueden usar cuantificadores de orden superior para definirlos, pero eso aumentaría la complejidad del cuantificador. Entonces, si quiero dar una respuesta breve a su pregunta sobre un cuantificador único, no lo sé.

$AC^0$$AC^0$$c$$e$$x$

Algunos comentarios adicionales:

$AC^0$

Para información, VO es realmente más poderoso que lo que usted dice; contiene toda la jerarquía analítica (por lo tanto, también toda la jerarquía aritmética). El resultado no se publica, ni se envía a ningún lugar, pero puede encontrarlo en mi página, www.milchior.fr/ho.pdf, sección 7, página 47.

$\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$$\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$$i$$X$$^i$$X$

$\phi(i)$$i$$k$$i>k$$\phi(i)$$k$$\phi(i)$$\forall i \phi(i)$$\forall i < k \phi(i)$

De lo contrario, ciertamente puede restringir el VO restringiendo el orden máximo aceptado; pero luego obtienes un lenguaje de "orden superior" (HO), y esto probablemente no sea lo que deseas.

Para responder a su comentario, supongo que debería hacer otra respuesta, hablando solo sobre Krom y Horn (tal vez debería hacerle una pregunta sobre eso a CSTheory)

Le sugiero que lea la sección 5.3, página 34, de mi artículo sobre el problema que encontré en Horn y Krom en la lógica de alto orden. Encontrará el mismo problema en orden variable (que es claramente un superconjunto de orden superior).

No sé si le prestaste atención, pero SO (krom) es igual a P cuando el primer orden es universal; de hecho, puede expresar un problema NP-completo si agrega una variable de primer orden existente. (No recuerdo el ejemplo que tenía antes, puedo intentar buscarlo si lo deseas)

No sé en qué se convertiría esta reestructuración sintáctica para la lógica de alto orden o de orden variable ... mi punto es que también debería pensar en una buena manera de restringir los cuantificadores, porque restringir la parte libre de cuantificador por sí sola no es útil ( al menos para las fórmulas de Krom)