A complexidade descritiva é um ramo da teoria da complexidade computacional e da teoria dos modelos finitos que caracteriza as classes de complexidade pelo tipo de lógica necessária para expressar as linguagens que as compõem. Por exemplo, PH, a união de todas as classes de complexidade da hierarquia polinomial, é precisamente a classe de linguagens que podem ser expressas por sentenças da lógica de segunda ordem. Essa conexão entre a complexidade e a lógica de estruturas finitas permite transferir resultados com facilidade de uma área para a outra, facilitando novos métodos de demonstração e fornecendo evidências adicionais de que as principais classes de complexidade são, de certo modo, "naturais" e não vinculadas às máquinas abstratas específicas utilizadas para defini-las. Isto é, ela fornece uma abordagem para a teoria da complexidade independente de modelo de máquina.

Especificamente, cada sistema lógico produz um conjunto de consultas expressíveis nele. As consultas — quando restritas a estruturas finitas — correspondem aos problemas computacionais da teoria da complexidade tradicional.

O primeiro resultado fundamental da complexidade descritiva foi o teorema de Fagin, demonstrado por Ronald Fagin em 1974. Ele estabeleceu que NP é precisamente o conjunto de linguagens expressíveis por sentenças da lógica de segunda ordem existencial; isto é, a lógica de segunda ordem que exclui a quantificação universal sobre relações, funções e subconjuntos. Diversas outras classes foram caracterizadas posteriormente de maneira análoga.

O arcabouço

Quando se utiliza o formalismo lógico para descrever um problema computacional, a entrada é uma estrutura finita, e os elementos dessa estrutura formam o domínio do discurso. Normalmente, a entrada é uma cadeia de caracteres (de bits ou sobre um alfabeto) e os elementos da estrutura lógica representam posições da cadeia, ou a entrada é um grafo e os elementos da estrutura lógica representam seus vértices. O comprimento da entrada é medido pelo tamanho da estrutura correspondente. Qualquer que seja a estrutura, pode-se assumir a existência de relações que podem ser testadas, por exemplo " é verdadeiro se e somente se existe uma aresta de para " (caso a estrutura seja um grafo), ou " é verdadeiro se e somente se a -ésima letra da cadeia for 1". Essas relações constituem os predicados do sistema de lógica de primeira ordem. Também se dispõe de constantes, que são elementos especiais da respectiva estrutura; por exemplo, se o objetivo for verificar a alcançabilidade em um grafo, escolhem-se duas constantes, (origem) e (destino).

Na teoria da complexidade descritiva, assume-se frequentemente a existência de uma ordem total sobre os elementos e a capacidade de testar a igualdade entre eles. Isso permite considerar os elementos como números: o elemento representa o número se e somente se existirem elementos tais que . Graças a isso, também se pode dispor do predicado primitivo "bit", onde é verdadeiro se e somente se o -ésimo bit da expansão binária de for 1. (Pode-se substituir a adição e a multiplicação por relações ternárias tais que é verdadeiro se e somente se , e é verdadeiro se e somente se ).

Visão geral das caracterizações de classes de complexidade Ao se restringir a análise a estruturas ordenadas dotadas de uma relação sucessor e de predicados aritméticos básicos, obtêm-se as seguintes caracterizações: A lógica de primeira ordem define a classe AC0 uniforme em logspace, correspondente às linguagens reconhecidas por circuitos de tamanho polinomial e profundidade limitada, o que equivale às linguagens reconhecidas por uma máquina de acesso aleatório concorrente em tempo constante. A lógica de primeira ordem estendida com operadores de maioria gera a classe TC0 uniforme em logspace. A lógica de primeira ordem estendida com operadores de fecho transitivo simétricos ou determinísticos gera L, a classe dos problemas solúveis em espaço logarítmico. A lógica de primeira ordem com um operador de fecho transitivo gera NL, os problemas solúveis em espaço logarítmico não determinístico. A lógica de primeira ordem com um operador de ponto fixo mínimo fornece P, os problemas solúveis em tempo polinomial determinístico, porém exclusivamente sobre estruturas ordenadas. Teorema de Fagin: a lógica de segunda ordem existencial gera NP. A lógica de segunda ordem universal (excluindo a quantificação existencial de segunda ordem) gera co-NP. A lógica de segunda ordem irrestrita corresponde à hierarquia polinomial PH. A lógica de segunda ordem com um operador de fecho transitivo (comutativo ou não) gera PSPACE, os problemas solúveis em espaço polinomial. A lógica de segunda ordem com um operador de ponto fixo mínimo fornece EXPTIME, os problemas solúveis em tempo exponencial. HO, a classe de complexidade definida pela lógica de ordem superior, é igual a ELEMENTARY.

Tempo subpolinomial

FO sem operadores Na complexidade de circuitos, a lógica de primeira ordem com predicados arbitrários demonstra-se equivalente a AC0, a primeira classe da hierarquia AC. De fato, existe uma tradução natural dos símbolos de FO para nós de circuitos, sendo e mapeados como portas e de tamanho . A lógica de primeira ordem em uma assinatura com predicados aritméticos caracteriza a restrição da família de circuitos AC0 àqueles construíveis em tempo logarítmico alternado. A lógica de primeira ordem em uma assinatura contendo apenas a relação de ordem corresponde ao conjunto das linguagens livres de estrela.

Lógica de fecho transitivo A lógica de primeira ordem ganha substancial poder expressivo quando estendida com um operador que computa o fecho transitivo de uma relação binária. A lógica de fecho transitivo resultante caracteriza o espaço logarítmico não determinístico (NL) sobre estruturas ordenadas. Esse resultado foi utilizado por Immerman para demonstrar que NL é fechada sob complementação (isto é, que NL = co-NL).

Ao restringir o operador de fecho transitivo ao fecho transitivo determinístico, a lógica resultante caracteriza exatamente o espaço logarítmico sobre estruturas ordenadas.

Fórmulas de Krom de segunda ordem Sobre estruturas que possuem uma função sucessor, NL também pode ser caracterizada por fórmulas de Krom de segunda ordem.

SO-Krom é o conjunto de consultas booleanas definíveis por fórmulas de segunda ordem na forma normal conjuntiva tais que os quantificadores de primeira ordem são todos universais e a parte livre de quantificadores da fórmula está na forma de Krom, o que significa que a fórmula de primeira ordem é uma conjunção de disjunções e, em cada "disjunção", há no máximo duas variáveis. Toda fórmula de Krom de segunda ordem é equivalente a uma fórmula de Krom de segunda ordem existencial.

SO-Krom caracteriza NL sobre estruturas com uma função sucessor.

Tempo polinomial Sobre estruturas ordenadas, a lógica de ponto fixo mínimo de primeira ordem captura PTIME:

Lógica de ponto fixo mínimo de primeira ordem FO[LFP] é a extensão da lógica de primeira ordem por um operador de ponto fixo mínimo, o qual expressa o ponto fixo de uma expressão monótona. Isso agrega à lógica de primeira ordem a capacidade de expressar recursão. O teorema de Immerman–Vardi, demonstrado de forma independente por Immerman e Vardi, estabelece que FO[LFP] caracteriza PTIME sobre estruturas ordenadas.

Permanece em aberto se existe uma lógica natural que caracterize PTIME sobre estruturas não ordenadas.

O teorema de Abiteboul–Vianu afirma que FO[LFP] = FO[PFP] sobre todas as estruturas se e somente se FO[LFP] = FO[PFP] sobre estruturas ordenadas; logo, se e somente se P = PSPACE. Esse resultado foi estendido para outros operadores de ponto fixo.

Fórmulas de Horn de segunda ordem Na presença de uma função sucessor, PTIME também pode ser caracterizada por fórmulas de Horn de segunda ordem.

SO-Horn é o conjunto de consultas booleanas definíveis com fórmulas de SO na forma normal disjuntiva tais que os quantificadores de primeira ordem são todos universais e a parte livre de quantificadores da fórmula está na forma de Horn, o que significa que se trata de uma conjunção de disjunções nas quais, em cada disjunção, todas as variáveis, com exceção de no máximo uma, aparecem negadas.

Essa classe é igual a P sobre estruturas com uma função sucessor.

Essas fórmulas podem ser transformadas em fórmulas prenexas na lógica de Horn de segunda ordem existencial.

Tempo polinomial não determinístico

Teorema de Fagin A demonstração de Ronald Fagin, em 1974, de que a classe de complexidade NP era caracterizada exatamente pelas classes de estruturas axiomatizáveis na lógica de segunda ordem existencial constituiu o marco inicial da teoria da complexidade descritiva.

Como o complemento de uma fórmula existencial é uma fórmula universal, segue-se imediatamente que co-NP é caracterizada pela lógica de segunda ordem universal.

SO, a lógica de segunda ordem irrestrita, é igual à hierarquia polinomial PH. Mais precisamente, tem-se a seguinte generalização do teorema de Fagin: o conjunto de fórmulas na forma normal prenexa onde quantificadores existenciais e universais de segunda ordem alternam-se vezes caracteriza o -ésimo nível da hierarquia polinomial.

Ao contrário da maioria das outras caracterizações de classes de complexidade, o teorema de Fagin e sua generalização não pressupõem uma ordenação total prévia sobre as estruturas. Isso ocorre porque a lógica de segunda ordem existencial é, por si só, suficientemente expressiva para quantificar sobre as ordens totais possíveis de uma estrutura utilizando variáveis de relação de segunda ordem.

Além de NP

Ponto fixo parcial é PSPACE A classe de todos os problemas computáveis em espaço polinomial, PSPACE, pode ser caracterizada estendendo-se a lógica de primeira ordem com um operador de ponto fixo parcial mais expressivo.

A lógica de ponto fixo parcial, FO[PFP], é a extensão da lógica de primeira ordem com um operador de ponto fixo parcial, que expressa o ponto fixo de uma fórmula caso este exista e retorna 'falso' caso contrário.

A lógica de ponto fixo parcial caracteriza PSPACE sobre estruturas ordenadas.

Fecho transitivo é PSPACE A lógica de segunda ordem pode ser estendida por um operador de fecho transitivo da mesma maneira que a lógica de primeira ordem, originando SO[TC]. O operador TC pode agora receber variáveis de segunda ordem como argumento. SO[TC] caracteriza PSPACE. Como a ordenação pode ser definida internamente na lógica de segunda ordem, essa caracterização não pressupõe estruturas previamente ordenadas.

Funções elementares A classe de complexidade de tempo ELEMENTARY de funções elementares pode ser caracterizada por HO, a classe de complexidade de estruturas que podem ser reconhecidas por fórmulas da lógica de ordem superior. A lógica de ordem superior é uma extensão da lógica de primeira ordem e da lógica de segunda ordem com quantificadores de ordens mais altas. Há uma relação direta entre a -ésima ordem e algoritmos não determinísticos cujo tempo de execução é limitado por uma torre de exponenciais de altura .

Definição Definem-se variáveis de ordem superior. Uma variável de ordem possui uma aridade e representa qualquer conjunto de -tuplas de elementos de ordem . Elas são habitualmente grafadas em letras maiúsculas com um número natural como expoente para indicar a respectiva ordem. A lógica de ordem superior é o conjunto de fórmulas de primeira ordem ao qual se adiciona quantificação sobre variáveis de ordens superiores; portanto, utilizam-se os termos definidos no artigo de FO sem redefini-los.

HO é o conjunto de fórmulas com variáveis de ordem no máximo . HO é o subconjunto de fórmulas da forma , onde é um quantificador e significa que é uma tupla de variáveis de ordem com a mesma quantificação. Assim, HO é o conjunto de fórmulas com alternâncias de quantificadores de ordem , iniciando com , seguidas por uma fórmula de ordem .