Saltar para o conteúdo

Geografia generalizada

Origem: Wikipédia, a enciclopédia livre.

Na teoria da complexidade computacional, generalizada a geografia é problema PSPACE-completo bem conhecido.

Geography é um jogo infantil que é bom para uma longa viagem de carro, onde os jogadores revezam entre si dizendo o nome de cidades ao redor do mundo. Cada cidade escolhida deve começar com a mesma letra que terminou o nome da cidade anterior. Repetição não é permitida. O jogo começa com uma cidade arbitrário e termina quando um jogador perde porque ele ou ela é incapaz de continuar.

Gráfico modelo

[editar | editar código-fonte]

Para visualizar o jogo, um gráfico direcionado pode ser construído cujos nós são cidades do mundo. Uma seta é adicionada a partir do nó N1 para o nó N2 se, e somente se, a cidade com rotulagem N2 começa com a letra que termina o nome da cidade com rotulagem N1. Em outras palavras, vamos desenhar uma seta de uma cidade para outra se a primeira pode levar para a segunda de acordo com as regras do jogo. Cada aresta alternativa no gráfico direcionado corresponde a cada jogador (para um jogo de dois jogadores). O primeiro jogador incapaz de estender o caminho perde. Uma ilustração do jogo (contendo algumas cidades no estado de Michigan) é mostrado na figura abaixo.

Num jogo de geografia generalizada (GG), podemos substituir o gráfico de nomes de cidades com um grafo direcionado arbitrário. O gráfico a seguir é um exemplo de um simples jogo de geografia.

Jogando o jogo

[editar | editar código-fonte]

Definimos P1 como o jogador que se move de primeira e P2 como o jogador de segundo e nomeamos os nós de N1 a Nn. Na figura acima, P1 tem uma estratégia vencedora, conforme segue: N1 aponta apenas para os nós de N2 e N3. Assim, o primeiro movimento de P1 deve ser uma dessas duas opções. P1 escolhe N2 (se P1 escolher N3, P2 vai escolher N9 já que é a única opção e P1 vai perder). Em seguida P2 escolhe N4 porque é a única escolha remanescente. P1 agora escolhe N5 e P2 , posteriormente, escolhe N3 ou N7. Independentemente da escolha de P2, P1 escolhe N9 e P2 não tem opções restantes e perde o jogo.

Declaração do problema

[editar | editar código-fonte]

O problema de determinar qual jogador tem uma estratégia vencedora em um simples jogo de geografia é PSPACE-completo. Suponha que

GG = { <G, b> | P1 tem uma estratégia vencedora para o jogo de geografia generalizada jogado no gráfico de G começando pelo nó b }.

Geografia generalizada está em PSPACE

[editar | editar código-fonte]

Para mostrar que GG ∈ PSPACE, apresentamos um algoritmo recursivo de espaço polinomial que determina qual jogador tem uma estratégia vencedora. Dada uma instância de GG, <G, niniciar> onde G é um gráfico direcionado e niniciar é o ínicio nó, o algoritmo de M continua da seguinte maneira:

Em M(<G, niniciar>):

  1. Medir o grau do nó niniciar. Se este grau é 0 e, em seguida, retornar rejeitar, porque não há movimentos disponíveis para o jogador.
  2. Construir uma lista de todos os nós, acessível a partir de niniciar por uma borda: n1, n2, ..., nj.
  3. Remova niniciar e todas as extremidades ligadas a ele a partir de G para formar G1.
  4. Para cada nó nj na lista n1, ..., ni, chamada de M(<G1, nj>).
  5. Se todas estas chamadas retornarem aceitar, então não importa que decisão P1 tome, P2 tem uma estratégia para vencer, daí retorna rejeitar. Caso contrário (se uma das chamadas retornar rejeitar) P1 tem uma escolha que vai negar qualquer estratégia bem sucedida para P2, então retorna aceitar.

O algoritmo M claramente decide GG. É em PSPACE, porque é o único local de trabalho polinomial não óbvio consumido na pilha de recursão. O espaço consumido pelo pilha de recursão é polinomial porque cada nível de recursão adiciona um único nó para a pilha, e há, no máximo, n níveis, onde n é o número de nós em G.

Geografia generalizada é PSPACE-díficil

[editar | editar código-fonte]

Para estabelecer o PSPACE-forte de GG, pode-se reduzir o problema do Jogo de fórmula (que é conhecido por ser PSPACE-forte) para GG em tempo polinomial (P). Em resumo, uma instância do problema do Jogo de fórmula consiste em um fórmula Booleana quantificada φ = ∃x1x2x3 ...Qxk(ψ) onde Q é ∃ ou ∀. O jogo é jogado por dois jogadores, o Pa e Pe, que alternam na  escolha de valores sucessivos de xi. Pe ganha o jogo se a fórmula ψ acaba sendo verdadeira, e Pum ganha, se ψ acaba falsa. A fórmula ψ é assumida estar na forma normal conjuntiva.

Nesta prova, assumimos que a lista quantificadora começa e termina com o qualificador existencial, ∃, para manter a simplicidade. Observe que qualquer expressão pode ser convertida para este formulário, adicionando variáveis de enchimento que não aparecem em ψ.

Através da construção de um grafo G como o mostrado acima, vamos mostrar qualquer instância do problema do Jogo de fórmula pode ser reduzida a uma instância de Geografia Generalizada, onde a melhor estratégia de P1 é equivalente ao de Pe, e a melhor estratégia para P2 é equivalente ao de Pa.

A cadeia vertical na esquerda dos nós foi projetada para imitar o procedimento de escolha de valores para as variáveis no Jogo de Fórmula. Cada estrutura de diamante corresponde a uma variável quantificada. Os jogadores revezam entre si para decidir caminhos em cada nó da ramificação. Já que assumimos que o primeiro quantificador seria existencial, P1 vai primeiro, selecionando a esquerda do nó se x1 é verdadeiro e o direito nó se x1 é falso. Cada jogador deve, então, ter turnos forçados e, em seguida, P2 escolhe um valor para x2. Estas atribuições se alternando continuam para o lado esquerdo. Depois que ambos os jogadores passam por todos os diamantes, é novamente a vez de P1, já que partimos do pressuposto de que o último quantificador é existencial. P1 não tem escolha, a não ser seguir o caminho para o lado direito do gráfico. Em seguida, é a vez de P2 fazer um movimento.

Quando o jogo chega no lado direito do grafo, é semelhante ao fim do jogo no jogo da fórmula. Lembre-se que o jogo da fórmula, Pe ganha se ψ é verdadeiro, enquanto que Pa ganha se ψ é falso. O lado direito do grafo garante que P1 seja vitorioso se, e somente se, Pe vencer, e que P2 vence se e somente se Pa vencer.

Primeiro vamos mostrar que P2 sempre ganha quando Pa ganha. Se Pa ganhar, ψ é falso. Se ψ é falso, não existe uma cláusula insatisfatória. P2 escolherá uma cláusula insatisfatória para ganhar. Em seguida, quando for a vez de P1, ele deve escolher um literal na cláusula escolhida por P2. Já que todos os literais da cláusula são falsos, eles não se conectam aos nós visitados anteriormente na cadeia vertical esquerda. Isso permite que P2 siga a conexão até o nó correspondente num  diamante da cadeia esquerda, e selecione-a. No entanto, o P1 agora é incapaz de selecionar um nó adjacente e perde.

Agora vamos mostrar que P1 sempre ganha quando Pe vence. Se Pe vence, ψ é verdadeiro. Se ψ é verdade, cada cláusula no lado direito do gráfico contém um literal verdadeiro. P2 pode escolher qualquer cláusula. Então P1 escolhe o literal que é verdadeiro. E porque ele é verdadeiro, o seu nó adjacente na vertical esquerda já foi selecionado, então P2 não tem movimentos para fazer e perde.

Consequências

[editar | editar código-fonte]

Dado que a GG é PSPACE-completo, nenhum algoritmo de tempo polinomial existe para um ótimo jogo no GG, a menos que P = PSPACE. No entanto, pode não ser tão fácil provar a complexidade de outros jogos, porque alguns jogos (como o xadrez) contém um número finito de jogo de posições — o que torna difícil (ou impossível) para formular um mapeamento para um problema PSPACE-completo. Apesar disso, a complexidade de alguns jogos podem ainda ser analisadas por generalização (por exemplo, para um tabuleiro n × n). Veja as referências para uma prova generalizada Go, como um corolário da prova da completude do GG.

  • Michael Sipser, Introduction to the Theory of Computation, PWS, 1997. 
  • David Lichtenstein and Michael Sipser, GO is polynomial Space Hard, Journal of the Association for Computing Machinery, April 1980.