P y complejidad descriptiva

10

En Complexity Zoo, dice [ 1 ] que, en complejidad descriptiva, PAG puede definirse mediante tres tipos diferentes de fórmulas, FO(LFPAG) que también es FO(norteO(1)) , y también como SO(HORnorte) .

Sin embargo, hay algunas excepciones, por ejemplo, mivminortenortemiss no puede expresarse por FP (FP tiene el mismo poder expresivo con LFP). ConortenortemiCtyovyoty y 2-Coloturunasiyolyoty no son definibles por la lógica de primer orden. Algunos problemas ni siquiera se pueden axiomatizar con un número finito de variables como mivminortenortemiss ,PAGmirFmiCt METROunatChyonortesol ,HunametroyoltonorteyoCyoty .

Immerman propuso que la lógica de punto fijo + conteo (FPC) puede ser una lógica posible para capturar P.

Sin embargo, Cai Furer, Immerman demostró que hay propiedades de gráficos de tiempo polinómico que no son expresables en FPC [ 2 ]. El problema de resolver ecuaciones lineales sobre el campo de dos elementos no se puede definir en lógica infinitaria con conteo [ 3 ]. Puede consultar [ 4 ] para obtener más detalles.

Entonces, ¿qué estructura lógica puede capturar P en general? La respuesta positiva es que una clase de estructuras finitas ordenadas es definible en la lógica de punto mínimo si, y solo si, es decidible en P por Immerman [ 5 ] y Vardi [ 6 ]. ¿Qué tal en el caso desordenado? ¿Puedes mostrar más contraejemplos de la declaración en el zoológico de complejidad?

Rupei Xu
fuente
2
Aquí hay un tutorial que ofrece una visión general de los resultados de esta pregunta en particular: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf
Denis
@ Denis Gracias, Denis! Este tutorial contiene más estructuras lógicas para P. Tradicionalmente, cuando hablamos de que un problema es solucionable en tiempo polinómico, pensamos que es "fácil". Sin embargo, las estructuras lógicas de P parecen tan complicadas, y todavía hay muchos casos desconocidos y problemas abiertos.
Rupei Xu
1
Sí, parece que el conjunto de problemas "fáciles" (es decir, P) no está tan bien estructurado y es difícil de caracterizar con algo como "los problemas fáciles son los que se pueden obtener de los problemas básicos A, B, C, combinado en formas X, Y ". Siempre hay problemas más fáciles que son de otro tipo y requieren algoritmos polinomiales inteligentes con nuevas ideas en ellos.
Denis

Respuestas:

2

Martin Grohe hizo progresos sustanciales en esta cuestión recientemente. Da una lógica que captura el tiempo polinómico en clases de gráficos incrustables en una superficie fija: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Editar: el caso general parece no estar resuelto (pero de ninguna manera estoy resuelto) Un experto en esto).

Hermann Gruber
fuente
Si. Hay muchos resultados de metateoremas algorítmicos (como el famoso teorema de Courcelle) que pueden capturar los casos fáciles, el siguiente enlace es un buen documento de encuesta. people.cs.umass.edu/~immerman/pub/… Sin embargo, esos resultados también tienen la restricción para las estructuras de gráficos en las que se ejecuta el problema, como árbol, ancho de árbol delimitado, gráficos planos, gráficos cerrados menores, etc. Hay ninguna estructura lógica completa puede capturar P en gráficos generales sin orden hasta ahora.
Rupei Xu
Supongo que el trabajo de Grohe es bastante especial porque en ese caso la lógica agota todo P en una clase de gráficos notablemente grande, es decir, no hay contraejemplos. Si lo hice bien, ser exhaustivo es la parte difícil. Los resultados de MSO que menciona no parecen tener esta característica. Pero mi experiencia en este aspecto es muy limitada, puedo estar equivocado aquí.
Hermann Gruber