Gadget (teoria da complexidade)

Na teoria da complexidade computacional, um gadget é um subconjunto de uma instância de um problema que simula o comportamento de uma das unidades fundamentais de um problema computacional diferente. Gadgets são normalmente utilizados para a construção de reduções de um problema computacional para outro, como parte da prova de NP-completude ou outros tipos de problemas mais dificeis. A técnica de design de componente é um método para a construção de reduções usando gadgets.

Szabó (2009)  faz uma busca no histórico do uso de gadgets em um  artigo  de 1954 na teoria dos grafos por WT Tutte, em que Tutte utiliza gadgets para reduzir o problema de encontrar um subgrafo com determinadas restrições de grau  para um problema de emparelhamento perfeito. No entanto, a terminologia "gadget" tem uma origem mais tarde, e não aparece no artigo de Tutte.

Exemplo

Redução NP-completa a partir de 3-satisfatibilidade em  3-coloração de grafos. Os gadgets para variáveis e cláusulas são mostrados no canto superior e inferior esquerdo, respectivamente; à direita é um exemplo da redução pela fórmula 3-CNF (x ∨ y ∨ ~ z) ∧ (~ x  ∨ ~ y ∨ z) com três variáveis e duas cláusulas.

Diversas provas de NP-completude são baseadas em reduções por mapeamento ao 3-satisfatibilidade, problema de determinar se existe uma determinada valoração para as variáveis de uma determinada fórmula booleana tal que esta valoração satisfaça esta fórmula em questão onde cada cláusula contém exatamente 3 literais. Uma redução deste problema a um problema difícil em grafos não direcionados, tais como o problema do ciclo Hamiltoniano ou da coloração de grafos, seria tipicamente baseada em gadgets sob a forma de subgrafos que simulam o comportamento das variáveis e cláusulas de um dado exemplo do 3-satisfatibilidade . Estes gadgets, serão colados uns aos outros para formar um único grafo, uma instância difícil para o problema em consideração.

Por exemplo, o problema de testar 3-coloração de grafos pode ser provado NP-completo por uma redução do 3-satisfatibilidade. A redução usa dois vértices especiais, classificados como "Terra" e "False", que não fazem parte de qualquer gadget. Como mostrado na figura, o gadget para uma variável x consiste de dois vértices ligados em triângulo com o vértice do terra; um dos dois vértices do dispositivo é marcado com x e o outro é marcado com a negação de x. O gadget para uma cláusula (t₀ ∨ t₁ ∨ t₂) é constituído de seis vértices, ligados uns aos outros, com os vértices representando os termos t₀, t₁, e t₂,  e aos vértices terra e falso pelas arestas mostradas. Qualquer fórmula 3-CNF pode ser convertida em um grafo por meio da construção de um gadget separado para cada uma das suas variáveis e cláusulas e ligando-os como mostrado.

Em qualquer 3-coloração do grafo resultante, pode-se designar  três cores  sendo elas verdadeiro, falso, ou terra, onde falso e terra são as cores dadas aos vértices falsos e terra (necessariamente diferentes, já que esses vértices são feitos adjacentes por construção) e verdadeiro é a cor não utilizada por qualquer destes vértices. Com um gadget variável, apenas duas cores são possíveis: o vértice rotulado com a variável deve ser de cor verdadeira ou falsa, e o vértice marcado com a negação da variável deve ser correspondentemente de cor falsa ou verdadeira. Desta forma, as atribuições válidas de cores para os gadgets variáveis ​​correspondem um para um em relação às  variáveis: o comportamento do gadget no que diz respeito à coloração simula o comportamento de uma variável em relação à atribuição verdadeira. Cada cláusula 3-coloração é valida se pelo menos um dos seus vértices adjacentes tem a cor verdadeira, e não pode ser válida se todos os seus vértices adjacentes forem de cor falso. Desta forma, a cláusula do gadget pode ser colorida se somente se a valoração correspondente satisfaz a cláusula, portanto, novamente o comportamento do gadget simula o comportamento de uma cláusula.

Reduções restritas

Agrawal et al. (1997) considerou o que eles chamavam de "uma forma radicalmente simples de redução de gadget", em que cada bit na descrição de um gadget pode depender apenas de um número limitado de bits da entrada, e usou estas reduções para provar a conjectura análoga de Berman-Hartmanis afirmando que todos os conjuntos NP-completos são polinomialmente isomorfos.

A definição padrão de NP-completude envolve redução por mapeamento em tempo polinomial: um problema em NP é, por definição NP-completo se todos os outros problemas em NP tem uma redução deste tipo a ele, e a maneira padrão de provar que um problema em NP é NP-completo é encontrar uma redução em tempo polinomial de um problema NP-completo conhecido a ele. Mas (em que Agrawal et al chamou de "um, fato curioso freqüentemente observado"), todos os conjuntos conhecidos por serem NP-completos naquele momento poderiam ser provados completos utilizando a noção mais forte de redução muitos-para-um AC⁰ , ou seja, reduções que podem ser calculadas por circuitos de tamanho polinomial, profundidade constante e sem limite na quantidade de entradas que pode receber ao mesmo tempo. Agrawal et ai. provou que todo problema NP-completo sob reduções AC⁰ é completo sob um tipo ainda mais restrito de redução, reduções muitos-para-um NC⁰ , usando circuitos de tamanho polinomial, profundidade constante e entrada limitada. Em uma redução NC⁰, cada bit de saida da redução pode depender somente de um número constante de bits de entrada.

A conjectura de Berman-Hartmanis é um problema não resolvido na teoria da complexidade computacional afirmando que todas as classes de problemas NP-completos são tempo-polinomial isomorfos. Isto é, se A e B são duas classes de problemas NP-completos, então existe uma redução de tempo polinomial um-para-um de A a B cuja inversa também é calculável em tempo polinomial. Agrawal et ai usou a equivalência entre as reduções AC⁰ e reduções NC⁰ para mostrar que todos os conjuntos completos para NP sob reduções AC⁰ são AC⁰-isomorfos.

Otimização de gadgets

Uma aplicação de gadgets é em provar resultados em dificuldade de aproximação, por redução de um problema que é conhecido por ser difícil para se aproximar a um outro problema cuja dificuldade deve ser provada. Nesta aplicação, há tipicamente, uma família de instâncias do primeiro problema em que há uma diferença nos valores da função, e em que é difícil determinar se dada uma instância, se sua  função está no lado de baixo ou no lado alto do intervalo. As reduções utilizadas nestas provas, e os gadgets utilizados nas reduções, deve preservar a existência deste intervalo, e a veracidade do resultado da aproximação derivado da redução dependerá de quão bem a diferença está relacionada.

Trevisan et ai. (2000) formalizou o problema de encontrar os intervalos em gadgets, para famílias de problema da satisfação de restrições no qual o objetivo é maximizar o número de restrições satisfeitas. Eles dão como exemplo uma redução de 3-satisfatibilidade a 2-satisfatibilidade por Garey, Johnson & Stockmeyer (1976), em que o gadget representando uma cláusula 3-SAT é composto por dez cláusulas 2-SAT, e em que uma atribuição verdade que satisfaz 3-SAT cláusula também satisfaz pelo menos sete cláusulas do gadget, enquanto uma atribuição de verdade que não consegue satisfazer uma cláusula 3-SAT também não satisfaz mais de seis cláusulas do gadget. Usando este gadget, e o fato de que (a menos que P = NP) não há nenhum esquema de aproximação de tempo polinomial para maximizar o número de cláusulas em 3-SAT em que uma atribuição de verdade satisfaz, se puder ser demonstrado que não há nenhum esquema de aproximação semelhante para MAX 2-SAT.

Trevisan et ai. mostrou que, em vários casos do problema de satisfação de restrição que estudou, os gadgets que conduzem aos possíveis resultados de aproximação  podem ser construídos automaticamente, como a solução para um problema de programação linear. As mesmas reduções à base de gadget também podem ser usadas na outra direção, para transferir algoritmos de aproximação de problemas mais fáceis em problemas mais difíceis. Por exemplo, Trevisan et ai. forneceu um gadget ideal para a redução de 3-SAT para uma variante ponderada de 2-SAT (que consiste em sete cláusulas 2-SAT ponderadas), que é mais forte que o de Garey, Johnson & Stockmeyer (1976); usando, juntamente com algoritmos de aproximação conhecidos de programação semidefinida para MAX 2-SAT, eles fornecem um algoritmo de aproximação para MAX 3-SAT com relação de aproximação 0,801, melhor do que algoritmos previamente conhecidos.