Considere o jogo a seguir em um gráfico ponderado direcionado com um chip em algum nó.
Todos os nós de são marcados por A ou B.
Existem dois jogadores Alice e Bob. O objetivo de Alice (Bob) é mudar o chip para um nó marcado por A (B).
Inicialmente, Alice e Bob têm e dólares, respectivamente.
Se um jogador estiver em uma posição perdida (ou seja, a posição atual do chip é marcada por uma letra oposta), ele pode mover o chip para um nó vizinho. Esse movimento custa alguns dólares (o peso da margem correspondente).
O jogador perde se estiver em uma posição perdida e não tiver dinheiro para consertá-lo.
Agora considere o idioma GAME que consiste em todos os gráficos ponderados direcionados (todos os pesos são números inteiros positivos), posição inicial do chip e maiúsculas de Alice e Bob que são dadas na representação unária
de modo que Alice tenha uma estratégia vencedora neste jogo.
O jogo de linguagem pertence a P . De fato, a posição atual do jogo é definida pela posição do chip e pelas capitais atuais de Alice e Bob, de modo que a programação dinâmica funciona (aqui é importante que as capitais iniciais sejam dadas na representação unária).
Agora considere a seguinte generalização deste jogo. Considere vários gráficos ponderados direcionados com um chip em cada gráfico. Todos os nós de todos os gráficos são marcados por A e B. Agora, Bob ganha se todas as fichas são marcadas por B e Alice vence se pelo menos uma ficha marcada com A.
Considere o idioma MULTIGAME que consiste em todos os gráficos , posições iniciais e maiúsculas e (na representação unária), de modo que Alice vença no jogo correspondente. Aqui é importante que as capitais sejam comuns para todos os gráficos, portanto, não são apenas vários GAMEs independentes.
Pergunta Qual é a complexidade do idioma MULTI-JOGOS? (Também pertence a P ou existem algumas razões para que esse problema seja difícil?)
UPD1 Neal Young sugeriu o uso da teoria de Conway. No entanto, não sei se é possível usar essa teoria para vários jogos com capital comum.
UPD2 Quero mostrar um exemplo que mostra que MULTI-JOGO não é muito simples. Vamos Alice dividir seu capital de para alguns termos (Ela vai usar dólares para gráfico -ésimo). Definir como o número mínimo de tal forma que em jogo -ésimo Bob vitórias se Alice e Bob tem e dólares respectivamente. Se (para alguma divisão ), então Alice vence. No entanto, o oposto não é verdadeiro. Considere duas cópias do gráfico a seguir (inicialmente o chip fica à esquerda A):
Para um gráfico, Bob vence se e ou se e . No entanto, para o jogo com duas cópias deste gráfico, Bob perde se e . Na verdade, Bob tem que gastar ou dólares para mudar ambos os chips a um nó marcado por . Então Alice pode mudar pelo menos um chip para um nó marcado por A. Depois disso, Bob não tem dinheiro para salvar sua posição.
UPD3 Como a pergunta para gráficos arbitrários parece difícil, considere gráficos específicos. Denote os nós de algum gráfico como . Minha restrição é a seguinte: para cada par existe aresta de até e não há aresta reversa. Também existe uma restrição para os custos das arestas: para a aresta para não é maior que de para .
fonte
Respostas:
Como a resposta de Steven Stadnicki não parece ter sido aceita pelo autor da pergunta, achei que ainda seria útil fornecer uma atualização: tenho uma redução de 3SAT para MULTI-JOGO. Eu não olhei atentamente a resposta de Steven ou segui o link que ele forneceu, mas com base na seguinte redução, não ficarei surpreso se o MULTI-JOGO for realmente PSPACE completo. No entanto, posso não me incomodar em estender esse resultado além da dureza NP.
Uma instância 3SAT consiste nas cláusulasC1 1, … , Cm , sendo cada cláusula no formato CEu= Leu 1∨ Leu 2∨ Leu 3 onde cada eueu k é uma das variáveis x1 1, … , Xn ou a negação de uma das variáveis.
Dada uma instância 3SAT, a redução cria uma instância MULTI-JOGO que consiste emn + 1 jogos - um para cada variável e outro jogo usado como um excesso de capital. Primeiro, definiremos a estrutura dos gráficos para cada jogo, depois examinaremos um exemplo e discutiremos a ideia central e, em seguida, descobriremos quais custos exatos serão atribuídos às arestas para manter a redução firme.
Primeiro, o gráfico de jogo variávelGj para cada variável xj :
Para cada literaleueu k de cláusula CEu , se eueu k= xj ou eueu k= ¬ xj , criar vértices marcados CEuTUMA e CEuFUMA marcada com A e vértices marcados CEuTB e CEuFB marcado com B. Adicione arestas ( T, CEuTA ) e( F, CEuFA ) com custos definidos emeueu k . (Vamos definireueu k mais tarde.)
Adicione arestas( CEuTA , CEuTB ) e ( CEuTA , CEuTB ) . Se eueu k= xj , defina o custo ( CEuTA , CEuTB ) como eueu k- 1 e ( CEuTA , CEuTB ) custo 's paraeueu k . Caso contrário definido( CEuTA , CEuTB ) 'custo s aeueu k e( CEuTA , CEuTB ) ' s custo paraeueu k- 1 .
O jogo do sumidouro de capital:
Isso é muito para absorver, por isso, espero que um exemplo torne isso um pouco mais digerível. Nossa instância 3SAT é a seguinte:
A redução transforma essa instância em 4 gráficos de jogos variáveis e 1 gráfico de capital capital. Nos diagramas abaixo, os vértices vermelhos são marcados com A (ou seja, são posições vencedoras para Alice) e os vértices cianos são marcados com B (são posições vencedoras para Bob).
Gráfico parax1 1 :
Gráfico parax2 :
Gráfico parax3 :
Gráfico parax4 :
Gráfico para capital capital:
A ideia é a seguinte:
Bob é forçado a fazer os primeirosn movimentos, a fim de perder posições perdidas nos n jogos variáveis. Cada movimento codifica uma atribuição de true ou false para a variável correspondente.
Alice terá capital suficiente para fazer exatamente 4 movimentos, cada um dos quais Bob precisará ter capital suficiente para corresponder para que Bob vença. AscEu valores e as eueu k valores devem ser escolhidos de modo que apenas estratégia vencedora possível de Alice é a seguinte, por alguma cláusula CEu :
(Ci?A denota CiTA ou CiFA , apenas um dos quais é alcançável em um determinado jogo variável após os movimentos de abertura de Bob.)
Se corresponde abertura de Bob para uma atribuição verdade que deixa alguma cláusulaCi insatisfeito, então Alice escolher Ci e implementação da estratégia acima dos custos Alice li1+li2+li3+ci capital para implementar e Bob o mesmo derrotar; Se, por outro lado Ci está satisfeito, então contra-jogo de Bob recebe um desconto de pelo menos 1 . Nosso objetivo na definição de ci e lik valores e as capitais iniciais de Alice e Bob é garantir que esse desconto seja o fator decisivo para a conquista de Alice ou Bob.
Para esse fim, definab=m+1 e defina
Capital inicial de Alice para9b10+b8 ,
e o capital inicial de Bob para9b10+b8+n−1.
Observe que todos esses valores são polinomiais emm , portanto, a instância MULTI-GAME gerada pela redução possui polinômio de tamanho no tamanho da instância 3SAT, mesmo que esses custos sejam codificados em unários.
Observe também que para cada cláusulaCi , li1+li2+li3+ci=9b10+b8 é o capital inicial de Alice. (Que também é 1 maior que o capital de Bob depois de fazer os primeiros n movimentos.)
Antes de tudo, fica imediatamente claro que, se a abertura de Bob define uma atribuição de verdade que deixa uma cláusulaCi insatisfeita, então Alice vence usando sua cláusula Ci estratégia dada acima.
Se a abertura de Bob atender a todas as cláusulas, podemos argumentar sobre as opções de Alice que excluem qualquer outra possibilidade de vitória de Alice. Observe que a ordem na qual Alice faz suas jogadas é irrelevante, pois as respostas de Bob são forçadas e o capital total que Bob exigirá para responder às jogadas de Alice é inalterado pela ordem das jogadas de Alice.
A partir desta fase, podemos desconsiderar ab10 e b8 termos nos custos de movimentação escolhido, como eles vão sempre somar 9 b10+ b8 . Desde Alice deve escolher exatamente um movimento no jogo dissipador de capital, suponha que o movimento é a CEuUMA . Em seguida, Alice (ignorando b10 e b8 Da) ∑3k = 1eu b2 k capital restante, e Bob tem 1 1 menos do que esta quantidade restante.
Argumentos semelhantes devem estabelecer que Alice deve selecionar os movimentos que custamli2 e li1 . Se satisfaz atribuição verdade de Bob Ci , então, mesmo esta estratégia não funciona, como o desconto Bob fica em uma das lik custos baseados compensa a 1 menos capital que ele tem depois de sua abertura.
Uma observação sobre a minha resposta anterior: é óbvio, em retrospectiva, que, para a variante TABLE-GAME de MULTI-JOGO definida nos comentários dessa resposta, um DP no estilo de mochila é suficiente para determinar qual jogador tem uma estratégia vencedora. Você pode argumentar que a melhor estratégia de Bob é sempre responder a um estado perdedor em uma determinada mesa de jogo com o investimento mínimo possível (isso não pode interromper um movimento subsequente para Bob que ele teria de outra forma) e, a partir daí, a ordem dos movimentos de Alice não importa. Torna-se então uma questão de escolher uma divisão do capital de Alice entre os jogos, de forma que a soma das respostas mínimas de vitória de Bob sobre esses jogos exceda seu orçamento, que pode ser reformulado como um problema no estilo de mochila, que possui um DP em tempo polinomial devido à representação unária de custos. (Minha recorrência na verdade seria '
Acontece que mesmo uma estrutura de árvore simples para cada jogo, com profundidade constante e realmente apenas um garfo significativo por jogo (ou seja, aqueles no início que forçam Bob a escolher uma tarefa de verdade) é suficiente para obter a dureza NP. Eu tive algumas idéias para me livrar dessa bifurcação inicial, que parou de alguma forma forçando Bob a investir uma quantia fixa relativamente grande de capital emn jogos, sem que Alice precisasse se comprometer com esses jogos com antecedência, mas obviamente desde que o TABLE-GAME está em andamento. P isso não é possível sem o garfo.
Não pensei muito no seu caso especial da UPD3 . Suspeito que também seja difícil para o NP, pelo fato de meus gadgets variáveis parecerem de relance como se eles fossem adaptáveis a essas restrições, mas provavelmente não analisarei mais.
fonte
Atualização: provavelmente incorreta, deixando por enquanto um registro de ter explorado uma avenida. Ver comentários.
Atualização 2: definitivamente incorreta.
Considere um gráfico da forma (B) -1-> (A) -1-> (B), ieG = ( V, E) V= { 1 , 2 , 3 } E= { ( 1 , 2 ) , ( 2 , 3 ) }
No entanto, a recorrência abaixo falha emM[ 3 , 2 , 2 ] : não há divisão dos fundos de Bob 2 - u , u entre os dois primeiros jogos e o terceiro jogo, de modo que, para todas as parcelas dos fundos de Alice u = 1 ou u = 2v , 2 - v M[ 2 , 2 - u , 2 - v ] = B W[ 3 , u , v ] = B u = 1 u = 2 M[ 2 , 2 - u , 2 ] = A u = 0 W[ 3 , u , 2 ] = A
Pré-cálculo
e
fonte
Pelos meus comentários acima, aqui está uma redução que eu acho que mostra que o problema é difícil para o PSPACE (e presumivelmente completo). Deixei[ n ] n + 1 n … 0 i + 1 Eu 0 ≤ i < n 0 0 0 0 n [ n ] ≥ n 0 0
Agora, considere o gráficoG com dois nós adicionais α e β α [i] β β [j] [k] j<k α β β [j] [k] [k] [i] {i∣{j∣k}}
fonte