No Zoológico da Complexidade, diz [ 1 ] que, na complexidade descritiva, pode ser definido por três tipos diferentes de fórmulas, que também é e também como .
No entanto, existem algumas exceções, por exemplo, não pode ser expressa por FP (FP tem o mesmo poder expressivo com LFP). e não são definíveis pela lógica de primeira ordem. Alguns problemas nem sequer podem ser axiomatizados com um número finito de variáveis como , , .
Immerman propôs que a Lógica de Ponto Fixo + Contagem (CPF) pode ser uma lógica possível para capturar P.
No entanto, Cai Furer, Immerman mostrou que existem propriedades de gráficos em tempo polinomial que não são expressáveis no CPF [ 2 ]. O problema de resolver equações lineares sobre o campo de dois elementos não é definível na lógica infinita com a contagem [ 3 ]. Você pode consultar [ 4 ] para mais detalhes.
Então, qual estrutura lógica pode capturar P em geral? A resposta positiva é que uma classe de estruturas finitas ordenadas é definível na lógica de menos pontos fixos se, e somente se, for decidível em P por Immerman [ 5 ] e Vardi [ 6 ]. Que tal no caso não ordenado? Você pode mostrar mais contra-exemplos da declaração no zoológico de complexidade?
Respostas:
Martin Grohe fez progressos substanciais nesta questão recentemente. Ele fornece um tempo polinomial de captura lógica em classes de gráficos incorporáveis em uma superfície fixa: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Edit: o caso geral parece não ter sido resolvido (mas não estou de forma alguma um especialista nisso).
fonte