En Complexity Zoo, dice [ 1 ] que, en complejidad descriptiva, puede definirse mediante tres tipos diferentes de fórmulas, que también es , y también como .
Sin embargo, hay algunas excepciones, por ejemplo, no puede expresarse por FP (FP tiene el mismo poder expresivo con LFP). y 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 , , .
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?
Respuestas:
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).
fuente