O que é dureza UG e como é diferente da dureza NP com base na conjectura de jogos exclusivos?

22

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?

Tsuyoshi Ito
fonte
+1 Muito bom. Obrigado Tsuyoshi por esclarecer esse importante conceito na teoria da complexidade.
Mohammad Al-Turkistany

Respostas:

15

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:

Jogos de conjecturas únicas. Para todas as constantes ε e δ , existe uma constante k tal que o problema único do jogo com os parâmetros k , ε e δ é NP-completo.

Considere os resultados do seguinte formulário:

(1) Assumindo a conjetura de jogos únicos, o problema X é difícil para o NP.

(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:

(2) existem constantes £ e ô tal que, para cada constante k , o problema único jogo com parâmetros k , ε , e δ é redutível a X .

É 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).

Tsuyoshi Ito
fonte
8
Isso parece análogo às duas declarações: "(1) Supondo que P! = NP, X não tem algoritmo de tempo polinomial" e "(2) X é NP-difícil". (2) implica (1), mas (1) não implica (2). Na prática, geralmente provamos (2), embora frequentemente digamos (1) explicar o significado da prova para pessoas não familiarizadas com a dureza da DN.
Robin Kothari
1
@TsuyoshiIto, você pode considerar aceitar sua própria resposta :). Na verdade, é incentivado, e essa é uma boa referência q / a para futuros googlers.
precisa
@ Suresh: Obrigado. Provavelmente sim, mas o sistema exige que eu espere 48 horas depois de postar a pergunta antes de aceitar minha própria resposta.
Tsuyoshi Ito
@ TsuyoshiIto: Ah, eu não percebi isso. parece bom.
precisa
@TsuyoshiIto: boa resposta clara! desculpe, não segui sua solicitação para fazer dos meus comentários uma resposta para a outra pergunta: eu estava ocupado, preguiçoso, parte não achava que a pergunta revisada era uma pergunta.
Sasho Nikolov