A complexidade da satisfação de restrição é a aplicação da teoria da complexidade computacional na satisfação de restrição. Foi principalmente estudado para discriminar as classes tratáveis e intratáveis da complexidade dos problemas da satisfação de restrição em domínios finitos.
Resolver um problema de satisfação de restrição num domínio finito é, normalmente, um problema NP-completo. A pesquisa mostrou um número de subcasos de tempo polinomial, a maioria obtido ao restringir tanto domínios permitidos ou restritos quanto a maneira como as restrições podem ser colocadas sobre as variáveis. A pesquisa também estabeleceu uma relação dos problemas da satisfação de restrição com problemas em outras áreas, como a teoria de modelo finitos ou banco de dados.
Visão Geral Estabelecer se um problema de satisfação de restrição num domínio finito tem solução é, em geral, um problema NP-completo. Esta é uma consequência de vários problemas NP completo sendo expresso como problemas de satisfação de restrição. Os outros problemas incluem o problema de satisfatibilidade boolena e coloração de grafos.
A tratabilidade pode ser obtida ao se considerar classes específicas de problemas de satisfação de restrição. Como exemplo, se um domínio é binário e todas as restrições são binárias, estabelecer a satisfatibilidade é um problema de tempo polinomial porque esse problema equivale a 2 – SAT, que é tratável. A pesquisa mostrou uma quantidade de subcasos tratáveis, algumas dessas classes são baseadas em restringir os domínios permitidos ou relações, algumas outras em restringir a forma como as restrições são colocadas sobre as variáveis, e algumas em ambas as formas de restrição.
Uma das linhas de pesquisa usou uma correspondência entre o problema de satisfação de restrição e o problema de estabelecer a existência de um homomorfismo entre duas estruturas relacionais. Tal correspondência foi usada para ligar a satisfação de restrição com tópicos que são, tradicionalmente, relacionados com a teoria de banco de dados.
Um problema considerado de pesquisa é acerca da existência de dicotomias entre os conjuntos de restrições. É a questão de: se um conjunto de restrição contém apenas restrições de tempo polinomiais e restrições NP completo, tal questão está solucionada para alguns conjuntos de restrições, mas ainda aberta em relação ao conjunto de todas as restrições baseado num domínio fixo e conjunto de relações, a partir de 2007. Isto é considerado para alguns autores a pergunta mais importante sobre a complexidade da satisfação de restrição.
Restrições Subcasos tratáveis dos problemas gerais da satisfação de restrição podem ser obtidos ao colocar restrições adequadas sobre os problemas. Várias formas de restrição foram consideradas.
Restrições estruturais e relacionais A tratabilidade pode ser tida ao restringir os domínios e restrições possíveis. Particularmente, há dois tipos de restrições a serem consideradas: restrições relacionais limitam o domínio e os valores que satisfaçam as restrições; restrições estruturais limitam a forma que as retrições são distribuídas sobre as variáveis. Mais precisamente, uma restrição relacional especifica uma linguagem de restrição, que é um domínio e um conjunto de relações sobre esse domínio. Um problema de satisfação de restrição atende essa restrição se ele tiver esse domínio especifico e a relação de cada restrição está no conjunto de relações dado. Ou seja, uma relação de restrição limita o domínio e o conjunto de valores satisfatórios de cada restrição, mas não como as restrições são colocadas sobre as variáveis. Isso é feito por restrições estruturais, estas podem ser checadas olhando somente para os escopos de restrições (suas variáveis), ignorando as suas relações (seu conjunto de valores satisfatórios).
Uma linguagem de restrição é tratável se existir um algoritmo polinomial resolvendo todos os problemas baseados na linguagem, isto é, usando o domínio e relações especificadas no domínio. Um exemplo de linguagem de restrição tratável é aquela de domínios e restrições binárias. Formalmente, essa restrição corresponde a permitir somente domínios de tamanho 2 e apenas restrições que tenham relação binária. Enquanto que o segundo fato implica que os escopos das restrições são binários, isso não é uma restrição estrutural, porque não proíbe qualquer restrição de ser colocada num par arbitrário de variáveis. Aliás, o problema se torna NP completo se qualquer restrição é levantada: restrições binárias e domínios ternários podem mostrar o problema do grafo colorido, ao passo que restrições ternárias e domínios binários podem expressar 3 – SAT; ambos problemas são NP – completo.
Um exemplo de uma classe tratável, definida em termos de restrição estrutural, é problemas acíclicos binários. Dada um problema de satisfação de restrição com apenas restrições binárias, seu grafo tem um vértice para cada variável e uma aresta para cada restrição; dois vértices são colocados se eles estão numa restrição. Se o grafo do problema é acíclico, o problema também é chamado de acíclico. O problema de satisfabilidade na classe dos problemas binários acíclicos é tratável, isso é uma restrição estrutural, pois não coloca nenhum limite no domínio ou nos valores específicos que satisfazem a restrição; ao contrário, restringe a forma como as restrições são colocadas sobre as variáveis.
Enquanto que restrições estruturais e relacionais são as mais usadas para derivar classes tratáveis de satisfação de restrição, existem algumas classes tratáveis que não podem ser definidas pela restrição relacional ou estrutural, apenas. As classes tratáveis definidas nos termos de linha de convexidade não podem ser definidas apenas em termos de relação ou estrutura, uma linha de convexidade depende de relação e também na ordem de vairáves (e, consequentemente, não pode ser verificada ao olhar somente para cada restrição por vez).
Restrições uniformes e não-uniformes Os subcasos obtidos ao restringir uma linguagem de restrição finita é chamado é problema não-uniforme. Tais problemas são considerados, principalmente, quando expressam uma satisfação de restrição em termos de problema de homomorfismo, como explicado abaixo. Problemas uniformes também foram definidos no conjunto de problemas homomórficos; um problema uniforme pode ser tido como a união entre uma coleção (possivelmente infinita) de problemas não-uniformes. Um problema uniforme feito a partir de um conjunto infinito de não-uniforme problemas pode ser intratável mesmo se todos esses não-uniforme problemas forem tratáveis.
Restrições baseadas em árvores Alguns consideram que restrições são baseadas na tratabilidade do problema de satisfaçao de restrição, no qual as restrições são todas binárias e formam uma Árvore (grafo) de variáveis. Isso é uma restrição estrutural, podendo ser verificado se olhar somente os escopos das restrições, ignorando os domínios e relações.
Esta restrição é baseada no grafo primário do problema, que é o grafo no qual os vértices são as variáveis do problema e as arestas representam a presença de uma restrição entre duas variáveis. Tratabilidade pode, no entanto, ser tida ao colocar a condição de ser uma árvore ao grafo primário dos problemas, que são reformulações do original.
Condições equivalentes Problemas de satisfação de restrição podem ser reformulados em termos de outros problemas, levando as condições equivalentes a tratabilidade. A reformulação mais usada é o problema do homomorfismo.
A satisfação de restrição e o problema do homomorfismo A ligação entre a satisfação de restrição e a teoria do banco de dados foi fornecida na forma de correspondência entre o problema de restrição de satisfabilidade e o problema de checar se existe homomorfismo entre duas estruturas relacionais. Uma estrutura relacional é uma representação matemática de um banco de dados: é um conjunto de valores e de relações sobre tais valores. Formalmente, , onde cada é a relação sobre , isto é, um conjunto de valores de tuplas de .
Uma estrutura relacional é diferente de um problema de satisfação de restrição uma vez que uma restrição é uma relação e uma tupla de variáveis. Também é diferente a forma em que eles são usados: para um problema de satisfação de restrição, achar uma tarefa satisfatória é o problema principal; para uma estrutura de relação o principal problema é achar a resposta para uma consulta.
O problema da satisfação de restrição é, no entanto, relacionado ao problema de estabelcer a existência de homomorfismo entre duas estruturas relacionais. Um homomorfismo é uma função dos valores da primeira relação aos valores da segunda que, quando aplicados a todos os valores da relação da primeira estrutura, transforma isso no subconjunto da relação correspondente da segunda estrutura. Formalmente, é um homomorfismo de para se for uma função de para de tal forma que, se então .
A correspondência direta entre o problema de satisfação de restrição e o problema do homomorfismo pode ser estabelecida. Para um dado problema de satisfação de restrição, pode-se construir um par de estruturas relacionais, a primeira codificação das variáveis e as assinaturas das restrições, a segunda codificação dos domínios e das relações das restrições. Satisfabilidade do problema de satisfação de restrição corresponde a encontrar um valor para cada variável tal que a substituição de um valor em uma assinatura torna uma tupla na relação da restrição. Isso é exatamente possível se essa avaliação é um homomorfismo entre as duas estruturas relacionais.
A correspondência inversa é o contrário: dadas duas estruturas relacionais, uma codifica os valores da primeira nas variáveis de um problema de satisfação de restrição, e os valores da segunda no domínio do mesmo problema. Para cada tupla de cada relação da primeira estrutura, há uma restrição tendo como valores a relação de correspondência da segunda estrutura. Desta forma, um homomorfismo corresponde a mapear cada escopo de cada restrição (cada tupla de cada relação da primeira estrutura) numa tupla na relação de restrição (uma tupla na relação correspondente a segunda estrutura).
Um problema de satisfação de restrição não-uniforme é uma restrição na qual a segunda estrutura de um problema de homomorfismo é fixo. Ou seja, cada estrutura relacional define um problema não-uniforme, dizendo se a estrutura relacional é homomórfica a ele. Uma restrição similar pode ser colocada na primeira estrutura: para cada primeira fixa, o problema homomórfico é tratável. Um problema de satisfação de restrição uniforme é uma restrição arbitrária para os conjuntos de estruturas das primeira e segunda estruturas do problema homomórfico.
Avaliação de consulta conjuntiva e contenção Como o problema do homomorfismo equivale a avaliação de consulta conjuntiva e consulta de contenção conjuntiva, esses dois problemas são equivalentes a satisfação de restrição também.
Avaliação de junção Cada restrição pode ser vista como uma tabela num banco de dados, onde as variáveis são interpretadas como atributos e a relação é o conjunto de registros na tabela. As soluções de um problema de satisfação de restrição são o resultado da junção interna dos quadros que representam suas restrições; assim, o problema da existência de soluções pode ser reformulado como o problema de verificar se o resultado de uma junção interna de certo número de tabelas é vazio.
Teoremas da dicotomia