Jogos de uma rodada com dois provadores (2P1R) são uma ferramenta essencial para a dureza da aproximação. Especificamente, a repetição paralela de jogos de uma rodada com dois provadores oferece uma maneira de aumentar o tamanho de uma lacuna na versão de decisão de um problema de aproximação. Veja a palestra de pesquisa de Ran Raz no CCC 2010 para uma visão geral do assunto.
A repetição paralela de um jogo tem a propriedade surpreendente de que, embora um verificador aleatório opere de forma independente, os dois jogadores podem jogar de maneira não independente para alcançar um sucesso melhor do que jogar cada jogo de forma independente. A quantidade de sucesso é delimitada acima pelo teorema da repetição paralela de Raz:
Teorema : Existe uma constante universal modo que, para cada jogo 2P1R com o valor e tamanho da resposta , o valor do jogo de repetição paralela é no máximo .G 1 - ϵ s G n ( 1 - ϵ c ) Ω ( n / s )
Aqui está um resumo do trabalho de identificação dessa constante :
- O artigo original de Raz prova .
- Holenstein melhorou isso para .
- Rao mostrou que é suficiente (e a dependência de é removida) para o caso especial de jogos de projeção.
- Raz deu uma estratégia para o jogo de ciclo ímpar que mostrou que o resultado de Rao é acentuado para jogos de projeção.
Por esse corpo de trabalho, sabemos . Minhas duas perguntas são as seguintes:
Pergunta 1: Os especialistas nesta área têm um consenso quanto ao valor exato de ?
Se se pensa que , existem jogos específicos que não são projetivos, mas também violam especificamente as propriedades extras dos jogos de projeção exigidos pela prova de Rao.
Pergunta 2: Se , quais jogos interessantes violam a estratégia de Rao e têm potencial para ser exemplos nítidos?
Pela minha própria leitura, parece que a propriedade mais importante dos jogos de projeção que Rao usa é que uma boa estratégia para repetição paralela não usaria muitas das respostas possíveis para certas perguntas. De alguma forma, isso está relacionado à localidade dos jogos de projeção.
fonte