Complexidade da satisfação de restrição

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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, $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$ , onde cada $R_{i}^{A}$ é a relação sobre $V$ , isto é, um conjunto de valores de tuplas de $V$ .

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, $h$ é um homomorfismo de $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$ para $B=(D,R_{1}^{B},\ldots ,R_{n}^{B})$ se for uma função de $V$ para $D$ de tal forma que, se $(x_{1},\ldots ,x_{k})\in R_{i}^{A}$ então $(h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}$ .

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Algumas linguagens de restrição (ou problemas não-uniformes) são conhecidas por corresponder a problemas solucionáveis em tempo polinomial, e algumas outras são tidas como expressões de um problema NP-completo. Todavia, é possível que algumas linguagens de restrição não sejam nenhuma das coisas. Isso é conhecido como o Teorema de Ladner, que se P não é igual a NP, então existem problemas em NP que não são nem tempo polinomial nem NP-difíceis. Desde 2007, não se sabe se tais problemas podem ser expressos como problema de satisfação de restrição com uma linguagem de restrição consertada. Se as linguagens de Ladner não são expressas dessa forma, o conjunto de todas as linguagens de restrição poderia ser dividido entre tempo polinomial e problemas NP-completos, isto é, tal conjunto apresentaria uma dicotomia.

Resultados parciais são conhecidos para alguns conjuntos de linguagens de restrição. O resultado mais conhecido é o Teorema de Dicotomia de Shaefer, que prova a existência da dicotomia num conjunto de linguagens de restrição num domínio binário. Mais precisamente, prova que a restrição de relação num domínio binário é tratável se todas as suas relações pertencerem a uma das seis classes, e é um NP-completo caso contrário. Bulatov provou o teorema da dicotomia para domínios de três elementos.

Outro teorema de dicotomia para linguagens de restrição é o Teorema de Hell-Nesetril, que mostra a dicotomia para problemas em restrições binárias com uma única relação simétrica fixa. Em termos do problema de homomorfismo, cada problema é equivalente a existência de um homomorfismo de uma estrutura relacional para um dado grafo não direcionado e fixo (um grafo não direcionado pode ser considerado como uma estrutura relacional com uma única relação simétrica binária). O Teorema de Hell-Nesetril prova que cada problema ou é tempo polinomial ou NP-completo, mais especificamente, o problema é um tempo polinomial se o grafo é 2-colorível, ou seja, se é bipartido, e é NP-completo caso contrário.

Condições suficientes para a tratabilidade[editar | editar código-fonte]

Alguns resultados de complexidade provam que algumas restrições são polinomiais sem provar que todas as outras possíveis restrições do mesmo tipo são NP-difícil.

Datalog[editar | editar código-fonte]

Uma condição suficiente para tratabilidade está relacionada com a expressividade em Datalog. Uma consulta booleana Datalog dá um valor verdadeiro para um conjunto de literais sobre um dado alfabeto, cada literal sendo uma expressão de forma $L(a_{1},\ldots ,a_{n})$ ; como resultado, uma consulta Booleana Datalog expressa um conjunto de conjuntos de literais, pois ele pode ser tido como semanticamente equivalente ao conjunto de todos os conjuntos de literais que avalia para verdade.

Por outro lado, um problema não-uniforme pode ser visto como uma forma de expressar um conjunto similar. Para um problema não-uniforme dado, o conjunto de relações que pode ser usado em restrições é fixo; como resultado, pode-se dar nomes originais $R_{1},\ldots ,R_{n}$ a eles. Um exemplo de tal problema não-uniforme pode ser escrito como um conjunto de literais de forma $R_{i}(x_{1},\ldots ,x_{n})$ . Entre esses casos/conjuntos de literais, alguns são satisfatórios e outros não; se um grupo de literais é satisfatório ou não isso depende das relações, que são especificadas pelos problemas não-uniforme. Inversamente, um problema não-uniforme diz quais conjuntos de literais representam instâncias satisfatórias e quais não representam. Assim que as relações são nominadas, um problema não-uniforme expressa um conjunto de conjuntos de literais: aqueles associados a instâncias satisfatórias ou não.

Uma condição suficiente de tratabilidade é que um problema não-uniforme é tratável se o conjunto de suas instâncias insatisfatíveis pode ser expresso por uma consulta booleana de datalog. Em outros termos, se o conjunto de conjuntos de literais que representam instâncias não satisfatórias de um problema não-uniforme é também um conjunto de conjuntos de literais que satisfazem uma consulta booleana de datalog, então o problema não-uniforme é tratável.

Consistência local[editar | editar código-fonte]

A satisfabilidade pode, algumas vezes, ser estabelecida através da aplicação de uma forma de consistência local e, então, checando a existência de um domínio vazio ou de uma relação de restrição. Isso é geralmente correto, porém um algoritmo de insatisfatibilidade incompleto: um problema pode ser insatisfatível mesmo se não se produz um domínio vazio ou uma relação de restrição. Para algumas formas de consistência local, esse algoritmo pode precisar também de um tempo exponencial. Porém, alguns problemas e para alguns tipos de consistência local, isso é correto e tempo polinomial

As condições a seguir exploram o grafo primário do problema, que tem um vértice para cada variável e uma aresta entre dois nós se as variáveis correspondentes estão numa restrição. As seguintes são condições em problemas de satisfação de restrição binários, onde se impõe consistência local e é tratável e também permite estabelecer a satisfabilidade:

impor consistência de arco, se o grafo primário é acíclico;
impor consistência de arco direcional para uma ordenação das variáveis, que faz o grafo ordernado das restrições tendo largura 1 (existe uma ordenação se e somente se o grafo primário é uma árvore, mas não todas as ordenações de uma árvore resulta numa largura 1);
impor uma forte consistência de caminho para uma ordenação de variáveis que faz com que o grafo primário induza largura 2.

Uma condição que se estende a última vale para problemas de satisfação de restrição não-binários. Ou seja, para todos os problemas para os quais existe uma ordenação que faz com que o grafo primário induza uma largura limitada por uma constante i, impondo forte i-consistência direcional é tratável e permite estabelecer a satisfabilidade.

Condições baseadas em árvore[editar | editar código-fonte]

Problemas de satisfação de restrição, compostos de restrições binárias que somente podem ser vistas como grafos, onde os vértices são variáveis e as arestas, representam a presença de restrição entre duas variáveis. Este grafo é chamado de Grafo de Gaifman ou grafo de restrição primário (ou, simplesmente, grafo primário) do problema.

Se o grafo primário do problema é acíclico, estabelecer a satisfabilidade do problema é um problema tratável. Isso é uma restrição estrutural, podendo ser verficado ao olhar apenas para os escopos das restrições, desconsiderando suas relações e o domínio. Um grafo acíclico é uma floresta, mas conectividade é assumida; como resultado, a condição que normalmente é considerada é que grafos primários são árvores.

Esse estabelecimento de problemas de satisfação de restrição como árvore é explorada por métodos, que convertem problemas em equivalentes que só contêm restrições binárias organizadas como árvores. As variáveis desses problemas correspondem a conjuntos de variáveis do problema original; um domínio é obtido considerando algumas das restrições do problema original cujo escopo é contido na correspondência original do conjunto de variáveis; restrições desses novos problemas representam igualdade de variáveis que são colocadas em dois conjuntos.

Se o grafo de um desses problemas equivalentes é uma árvore, o problema pode ser solucionado de forma eficiente. Por outro lado, produzir um problema equivalente pode não ser eficiente, devido a dois fatores: a necessidade de determinar os efeitos combinados de um grupo de restrições sobre um conjunto de variáveis e a necessidade de armazenar todas as tuplas de valores de satisfazem um dado grupo de restrições.

Condição necessária para a tratabilidade[editar | editar código-fonte]

Uma condição necessária para a tratabilidade de uma linguagem de restrição baseada num gadget universal foi provada. Tal gadget universal é um problema de satisfação de restrição particular que foi, inicialmente, definido por uma questão de expressar novas relações pela projeção.

O gadget universal[editar | editar código-fonte]

Uma relação que não está presente numa linguagem de restrição pode ser “simulada” por restrições, usando as relações na linguagem. Particularmente, uma nova relação pode ser criada colocando-se um conjunto de restrições e usando somente algumas de suas variáveis. Se todas as outras restrições usarem apenas essas variáveis, esse conjunto de restrição força essas variáveis a apenas assumir valores específicos, simulando, praticamente, uma nova relação.

Cada problema de satisfação de restrição e subconjuntos de suas variáveis definem uma relação, que é composta por todas as tuplas de valores das variáveis que podem ser estendidas as outras variáveis para se ter a solução. Tecnicamente, tal relação é obtida por meio da projeção da relação tendo as soluções como linhas sobre as variáveis consideradas.

O gadget universal é baseado na observação de que cada relação que contém $k$ -tuplas pode ser definida projetando uma relação que contém todas as colunas possíveis de $k$ elementos do domínio. Como exemplo, as tabelas a seguir mostra tal projeção:

a b c d e f g h             b d
---------------             ---
1 1 1 1 0 0 0 0        ->   1 1
1 1 0 0 1 1 0 0             1 0
1 0 1 0 1 0 1 0             0 0

Se a tabela da esquerda é o conjunto de soluções de um problema de satisfação de restrição, suas variáveis $b$ e $d$ são restritas aos valores da tabela à direita. Como resultado, o problema de satisfação de restrição pode ser usado para definir uma restrição cuja relação é a tabela na direita, que poderá não ser em linguagem de restrição.

Como resultado, se um problema de satisfação de restrição tem na tabela da esquerda seu conjunto de soluções, cada relação pode ser expressa por meio de uma projeção sobre um conjunto de variáveis apropriado. Uma forma de tentar obter tal tabela como conjunto de soluções é colocar cada restrição possível que não está violada pelas soluções necessárias.

Como exemplo, se a linguagem contém a relação binária representando a disfunção booleana (uma relação contendo todas tuplas de dois elementos que contém ao menos um 1), essa relação é colocada como uma restrição $a$ e $b$ , porque seus valores na tabela acima são $(1,1)$ , $(1,1)$ de novo e $(1,0)$ . Como todos esses valores satisfazem a restrição, esta é colocada. Por outro lado, uma restrição com essa relação não é colocada em $b$ e $d$ , uma vez que a restrição da tabela acima para essas duas variáveis contém $(0,0)$ como terceira linha, e tal avaliação viola a restrição.

O gadget universal de ordem $k$ é o problema de satisfação de restrição contendo todas as restrições que podem ser colocadas para se ter a tabela acima. As soluções do gadget universal incluem as linhas dessa tabela, mas também podem conter outras linhas. Se as soluções são exatamente as linhas da tabela acima, cada relação pode ser expressa pela projeção de um subconjunto de variáveis. No entanto, mesmo se as soluções incluírem outras linhas, algumas relações podem ainda ser expressas. Um dos atributos do gadget universal é que ele é capaz de expressar, ao projetar, cada relação que pode ser mostrada com uma projeção de um problema de satisfação de restrição arbitrário, baseado na mesma linguagem. Mais precisamente, o gadget universal de ordem $k$ expressa todas as relações de linhas $k$ que podem ser mostradas na linguagem de restrição.

Dada uma relação especifica, sua expressabilidade na linguagem pode ser verificada considerando uma lista de variáveis arbitrárias cujas colunas na tabela acima (as soluções “ideais” para o gadget universal) forma aquela relação. A relação pode ser expressa na linguagem se e somente se as soluções do gadget universal coincidir com a relação quando projetados sobre a lista de variáveis. Em outras palavras, pode-se checar a expressabilidade selecionando variáveis “como se” as soluções do gadget universal fossem como na tabela e, então, checar se a restrição das soluções “reais” é realmente a mesma da relação. No exemplo acima, a expressabilidade da relação na tabela da direita pode ser vista olhando se as soluções do gadget universal, quando limitadas às variáveis $b$ e $d$ , são exatamente as linhas da tabela.

Soluções como funções no gadget universal[editar | editar código-fonte]

Uma condição necessária para a tratabilidade pode ser vista em termos do gadget universal. As soluções de tal gadget podem ser colocadas na tabela a seguir:

a b c d e f g h
---------------
1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0    (soluções que existem por definição)
1 0 1 0 1 0 1 0
---------------
....
1 0 0 1 1 1 0 0    (outras soluções são possíveis)
....

Essa tabela é feita em duas partes. A primeira contém as soluções que existem pela definição desse problema; a segunda (que pode estar vazia) contém todas as outras soluções. Como as colunas da tabela estão, por definição, associadas as possíveis k-tuplas de valores do domínio, cada solução pode ser vista como uma função de uma k-tupla de elementos para um único elemento.

A função correspondente a uma solução pode ser calculada da primeira parte da tabela acima e a solução. Como exemplo, para a última solução marcada na tabela, essa função pode determinar como argumentos $1,0,1$ da seguinte forma: primeiro, esses três valores são a primeira parte da linha “c” na tabela; o valor da função é o valor da solução na mesma coluna, ou seja, 0.

Uma condição necessária para a tratabilidade é a existência de uma solução para um gadget universal de alguma ordem que é parte de algumas classes de funções. Esse resultado, no entanto, só é válido para linguagens reduzidas, que serão definidas abaixo.

Funções Sigmóides e domínios reduzidos[editar | editar código-fonte]

Funções sigmóides são funções usadas para reduzir o tamanho do domínio de uma linguagem de restrição. Tal função é definida em termos de uma partição do domínio e um elemento representativo para cada conjunto na partição. Uma função sigmóide mapeia todos os elementos de um conjunto na partição para o elemento representante desse conjunto. Para tal função sendo uma sigmóide é também preciso que, aplicando a função para todos os elementos da relação da tupla na linguagem, produza outra tupla na relação. A partição é assumida de conter, ao menos, um conjunto de tamanho maior que outro.

Formalmente, dada uma partição $D_{1},\ldots ,D_{n}$ do domínio $D$ contendo, ao menos, um conjunto de tamanho maior que outro, uma função sigmóide é uma função $s:D\rightarrow D$ tal que $s(x)=s(y)$ para cada $x,y$ na mesma partição, e para cada tupla $\langle x_{1},\ldots ,x_{n}\rangle \in R$ que detém $\langle s(x_{1}),\ldots ,s(x_{n})\rangle \in R$ .

Para problemas de restrição numa linguagem de restrição existe uma função sigmóide, o domínio pode ser reduzido pela função sigmóide. Cada elemento num conjunto na partição pode ser realocada com o resultado de aplicar a função sigmóide nele, como esse resultado é garantido de satisfazer ao menos todas as restrições que foram satisfeitas pelo elemento. Como resultado, todos os elementos não representativos podem ser removidas da linguagem de restrição.

Linguagens de restrição para as quais não existe funções sigmóides são chamadas de linguagens reduzidas, essas linguagens são aquelas que todas as reduções por funções sigmóides já foram realizadas.

A condição necessária para a tratabilidade[editar | editar código-fonte]

A condição necessária para a tratabilidade baseada no gadget universal vale para linguagens reduzidas. Essa linguagem é tratável se o gadget universal tem uma solução que, quando vista como função na forma acima especificada, é ou uma função constante, uma função de maioria, uma função binária indepotente, uma função afim, ou uma semi-projeção.

Referências[editar | editar código-fonte]

Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
Vardi, Moshe Y. (2000). "Constraint Satisfaction and Database Theory: a Tutorial". PODS 2000. pp. 76–85.
Bulatov, Andrei A. (2006). "A dichotomy theorem for constraint satisfaction problems on a 3-element set". Journal of the ACM 53 (1): 66–120. doi:10.1145/1120582.1120584.