Existem muitos resultados de inadequação que se baseiam na conjetura de jogos únicos. Por exemplo,
Assumindo a conjectura exclusiva dos jogos, é NP difícil aproximar o problema de corte máximo dentro de um fator R para qualquer R > R GW constante .
(Aqui R GW = 0,878… é a taxa de aproximação do algoritmo de Goemans – Williamson.)
No entanto, algumas pessoas preferem usar o termo " UG-hard " como:
É difícil UG aproximar o problema de corte máximo dentro de um fator R para qualquer R > R GW constante .
O último é apenas uma abreviação para o primeiro, ou eles significam afirmações diferentes?
Respostas:
Uma versão anterior desta resposta foi postada originalmente como resposta à pergunta " Consequências de jogos únicos serem um problema de NPI " pelo NicosM. Como se descobriu que não respondeu o que ele queria perguntar, mudei para esta pergunta.
Resposta curta: significam afirmações diferentes. O último implica o primeiro, mas o primeiro não implica necessariamente o último.
Resposta longa: Lembre-se de que o problema exclusivo do jogo é o seguinte problema promissor.
Problema de jogo único com os parâmetros k ∈ℕ e ε , δ > 0 (1− ε > δ )
Instância : Um jogo único de dois jogadores G, com uma rodada, com tamanho de etiqueta k .
Sim-promessa : G tem valor pelo menos 1− ε .
Sem promessa : G tem valor no máximo δ .
A conjectura de jogos exclusivos afirma:
Considere os resultados do seguinte formulário:
(Um exemplo de X é o problema de aproximar o corte máximo dentro de algum fator constante R > R GW .)
A maioria (se não todos) dos resultados do formulário (1) provam o seguinte fato:
É fácil verificar que (2) implica (1). No entanto, (2) implica mais de (1): por exemplo, suponha que um dia possamos provar que uma variante da conjectura exclusiva de jogos em que “NP-complete” é substituída por “ GI- hard”. Então (2) implica esse X também é resistente a GI. (1) não implica isso. É por isso que algumas pessoas consideram que a afirmação (1) não é a melhor maneira de afirmar o teorema: (1) é mais fraca do que aquilo que é realmente provado, e a diferença pode ser importante.
Embora (2) seja uma afirmação mais precisa do que é provado, é claramente um bocado. É por isso que as pessoas sugerem uma abreviação para isso: “O problema X é difícil para os UG” é uma abreviação para (2).
fonte