P e Complexidade Descritiva

10

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 .PFO(LFP)FO(nO(1))SO(HORN)

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 , , .EvennessConnectivity2colourabilityEvennessPerfect MatchingHamiltonicity

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?

Rupei Xu
fonte
2
Aqui está um tutorial dando uma visão geral dos resultados sobre esta questão específica: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf
Denis
@ Denis Obrigado, Denis! Este tutorial contém mais estruturas lógicas para P. Tradicionalmente, quando falamos sobre um problema que pode ser resolvido em tempo polinomial, achamos que é "fácil". No entanto, as estruturas lógicas de P parecem muito complicadas, e ainda existem muitos casos desconhecidos e problemas em aberto.
Rupei Xu 11/02/19
11
Sim, parece que o conjunto de problemas "fáceis" (ou seja, P) não é tão bem estruturado e difícil de caracterizar com algo como "os problemas fáceis são aqueles que podem ser obtidos a partir dos problemas básicos A, B, C, combinado das maneiras X, Y ". Sempre há problemas mais fáceis de outro tipo e requerem algoritmos polinomiais inteligentes, com novas idéias.
Denis

Respostas:

2

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).

Hermann Gruber
fonte
Sim. Existem muitos resultados de meta-teoremas algorítmicos (como o famoso teorema de Courcelle) podem capturar os casos fáceis, o link a seguir é um bom artigo de pesquisa. people.cs.umass.edu/~immerman/pub/… No entanto, esses resultados também têm a restrição para as estruturas gráficas nas quais o problema é executado, como árvore, largura de árvore limitada, gráficos planares, gráficos menores fechados etc. Existem nenhuma estrutura lógica completa pode capturar P em gráficos gerais sem ordem até o momento.
Rupei Xu
Eu acho que o trabalho de Grohe é bastante especial porque, nesse caso, a lógica esgota todo P em uma classe notavelmente grande de gráficos, ou seja, não há contra-exemplos. Se eu entendi direito, ser exaustivo é a parte difícil. Os resultados do MSO mencionados não parecem ter esse recurso. Mas minha experiência nesse aspecto é muito limitada, posso estar errado aqui.
Hermann Gruber