Conjectura de jogos únicos

Problema de Ciência da Computação em aberto:

Prove ou refute a Conjectura de Jogos Únicos.
(mais problemas em aberto da Ciência da Computação)

Na teoria da complexidade computacional, a Conjectura de Jogos Únicos é uma conjectura feita por Subhash Khot em 2002. A conjectura postula que o problema de determinar o valor aproximado de um determinado tipo de jogo, conhecido como um jogo único, tem complexidade algorítmica NP-difícil. Ele tem amplas aplicações na teoria da dificuldade de aproximação. Se isso é verdade, então para muitos problemas importantes não só é impossível obter uma solução exata em tempo polinomial (tal como postulado pelo problema P versus NP), mas também é impossível obter uma boa aproximação de tempo polinomial. Os problemas para os quais tal resultado de inaproximabilidade se mantém incluem problemas de satisfação de restrições que surgem em uma ampla variedade de disciplinas.

A conjectura é incomum, de forma que o mundo acadêmico parece igualmente dividido sobre ela ser verdadeira ou não.

Formulações

A conjectura de jogos únicos pode ser declarada em uma série de maneiras equivalentes.

Cobertura de etiqueta única

A seguinte formulação da conjectura de jogos únicos é frequentemente utilizada na dificuldade de aproximação. A conjectura postula a NP-dificuldade do seguinte problema de promessa conhecido como cobertura de rótulo com restrições exclusivas. Para cada aresta, as cores nos dois vértices são restritas a alguns pares ordenados. Em particular, restrições exclusivas significam que, para cada aresta, nenhum dos pares ordenados têm a mesma cor para o mesmo nó.

Isso significa que uma instância de cobertura de rótulo com restrições exclusivas sobre um alfabeto de tamanho k pode ser representada como um grafo direcionado, juntamente com uma coleção de permutações π_e: [k] → [k], uma para cada aresta e do grafo. Uma atribuição para uma instância de cobertura de de rótulo dá para cada vértice de G um valor no conjunto [k] = {1, 2, ... k}, muitas vezes chamado de "cores."

• 
  Um exemplo de cobertura de rótulo único. Os 4 vértices podem ter cores vermelho, azul e verde atribuídas, satisfazendo as restrições em cada aresta.
• 
  Uma solução para o exemplo de cobertura de rótulo único.

Tais instâncias são fortemente restringidas, no sentido de que a cor de um vértice define exclusivamente as cores dos seus vizinhos e, assim, por todo seu componente conectado. Logo, se a instância de entrada admite uma atribuição válida, então tal atribuição pode ser encontrada de forma eficiente, iterando-se por todas as cores de um único nó. Em particular, o problema de decidir se uma dada instância admite uma atribuição satisfatível pode ser resolvido em tempo polinomial.

• 
  Um exemplo de cobertura de rótulo único que não permite uma atribuição satisfatória.
• 
  Uma atribuição que satisfaz todas as arestas, exceto as arestas grossas. Assim, esse exemplo tem valor 3/4.

O valor de uma instância de cobertura de rótulo único é a fração de restrições que podem ser satisfeitas por qualquer atribuição. Para instâncias satisfatíveis, esse valor é 1 e é fácil de encontrar. Por outro lado, parece ser muito difícil determinar o valor de um jogo insatisfatível, mesmo aproximadamente. A conjectura de jogos únicos formaliza essa dificuldade.

Mais formalmente, o problema de cobertura de rótulo de lacuna com restrições únicas (c, s) é o seguinte problema de promessa (L_sim, L,_n):

• L_sim = {G | Alguma atribuição satisfaz pelo menos uma c-fração de restrições em G}
• L_n = {G | Toda atribuição satisfaz, no máximo, uma s-fração de restrições em G}

onde G é uma instância do problema de cobertura de rótulo com restrições exclusivas.

A conjectura de jogos únicos afirma que, para cada par suficientemente pequeno de constantes ε, δ > 0, existe uma constante k tal que o problema de cobertura de rótulo de lacuna com restrições únicas (1 - δ, ε), sobre o alfabeto de tamanho k, é NP-difícil.

Em vez de gráficos, o problema de cobertura de rótulo pode ser formulado em termos de equações lineares. Por exemplo, suponha que tenhamos um sistema de equações lineares sobre os inteiros módulo 7:

${\displaystyle }$

Esse é um exemplo do problema de cobertura de rótulo com restrições exclusivas. Por exemplo, a primeira equação corresponde à permutação π_{(1, 2)}, onde π_{(1, 2)}(x₁) = 2x₂ módulo 7.

Sistemas de prova dois-provadores

Um jogo único, é um caso especial de um jogo de duas rodadas com dois-provadores (2P1R). Um jogo de duas rodadas com dois-provadores tem dois jogadores (também conhecidos como provadores) e um árbitro. O árbitro envia a cada jogador uma pergunta retirada de uma distribuição de probabilidade conhecida, e cada jogador tem de enviar uma resposta. As respostas vêm de um conjunto de tamanho fixo. O jogo é especificado por um predicado que depende das perguntas enviadas para os jogadores e as respostas fornecidas por eles.

Os jogadores podem decidir sobre uma estratégia de antemão, embora eles não possam se comunicar uns com os outros durante o jogo. Os jogadores ganham se o predicado é satisfeito por suas perguntas e as suas respostas.

Um jogo de duas rodadas com dois-provadores é chamado de um jogo único, se para cada par de perguntas e todas as respostas para a primeira pergunta, há exatamente uma resposta para a segunda pergunta, que resulta em uma vitória para os jogadores, e vice-versa. O valor de um jogo é a probabilidade de vitória máxima para os jogadores sobre todas as estratégias.

A conjectura de jogos únicos afirma que, para cada par de constantes suficientemente pequeno ε, δ > 0, existe uma constante k tal que o seguinte problema de promessa (L_sim, L_não) é NP-difícil:

• L_sim = {G | o valor de G é, pelo menos, 1 − δ}
• L_n = {G | o valor de G é no máximo ε}

onde G é um jogo único, cujas respostas vêm de um conjunto de tamanho k.

Provas probabilisticamente verificáveis

Como alternativa, a conjectura de jogos únicos postula a existência de um certo tipo de prova probabilisticamente verificável para os problemas em NP.

Um jogo único pode ser visto como um tipo especial de prova probabilisticamente verificável não-adaptativa com complexidade de consulta de 2, onde, para cada par de possíveis consultas do verificador e cada resposta possível para a primeira consulta, há exatamente uma possível resposta para a segunda consulta que faz o verificador aceitar, e vice-versa.

A conjectura de jogos únicos afirma que, para cada par de constantes suficientemente pequeno ε, δ > 0, existe uma constante K tal que cada problema em NP tem uma prova probabilisticamente verificável sobre um alfabeto de tamanho K com completude 1 - δ, solidez ε e complexidade de aleatoriedade O(log(n)), que é um jogo único.

Relevância

Resultados approximados supondo que P ≠ NP versus a UGC

Problema	Poli.-tempo aprox.	NP dificuldade	UG dificuldade
2-SAT Máx	0.940...	0.954... + ε	0.940... + ε
Corte Máximo	0.878...	0.941... + ε	0.878... + ε
Cobertura de Vértices Mínima	2	1.360... − ε	2-ε
Aleatoriedade	1/3	47/48	1/3 + ε

A conjectura de jogos únicos foi introduzida por Subhash Khot em 2002, a fim de fazer progressos em certas questões na teoria da dificuldade de aproximação.

A veracidade da conjectura de jogos únicos implica a otimicidade de muitos algoritmos de aproximação conhecidos (supondo que P ≠ NP). Por exemplo, a taxa de aproximação obtida pelo algoritmo de Goemans e Williamson para aproximar o corte máximo em um grafo é ótima para qualquer constante aditiva, assumindo a conjectura de jogos únicos e P ≠ NP.

Uma lista de resultados cuja conjectura de jogos únicos é conhecida por implicar é mostrada na tabela à direita, juntamente com os melhores resultados para o mais fraco dos pressupostos, de que P ≠ NP. Uma constante de c + ε ou c − ε significa que o resultado vale para cada constante (com relação ao tamanho do problema) estritamente maior que ou menor que c, respectivamente.

Discussão e alternativas

Atualmente, não há um consenso sobre a veracidade da conjectura de jogos únicos. Certas formas mais fortes da conjectura foram refutadas.

Uma forma diferente da conjectura postula que distinguir o caso de quando o valor de um jogo único é, no mínimo, 1 − δ a partir do caso de quando o valor é, no máximo, ε é impossível para algoritmos de tempo polinomial (mas talvez não NP-difícil). Esta forma de conjectura, ainda seria útil para aplicações na dificuldade de aproximação.

A constante δ > 0 nas formulações da conjectura acima é necessária, a menos que P = NP. Se o requisito de exclusividade é removido, a instrução correspondente é conhecida por ser verdadeira pelo teorema de repetição paralela , mesmo quando δ = 0.

Karpinski e Schudy construíram esquemas de aproximação de tempo linear para exemplos densos de problemas de jogos únicos.

Em 2010, Arora, Barak, e Steurer encontraram um algoritmo de aproximação de tempo sub-exponencial para o problema de jogos únicos.

Bibliografia

• Khot, Subhash (2010), «On the Unique Games Conjecture», Proc. 25th IEEE Conference on Computational Complexity (PDF), pp. 99–121, doi:10.1109/CCC.2010.19