Geografia generalizada

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

Introdução

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

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ó N₁ para o nó N₂ se, e somente se, a cidade com rotulagem N₂ começa com a letra que termina o nome da cidade com rotulagem N₁. 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

Definimos P₁ como o jogador que se move de primeira e P₂ como o jogador de segundo e nomeamos os nós de N₁ a N_n. Na figura acima, P₁ tem uma estratégia vencedora, conforme segue: N₁ aponta apenas para os nós de N₂ e N₃. Assim, o primeiro movimento de P₁ deve ser uma dessas duas opções. P₁ escolhe N₂ (se P₁ escolher N₃, P₂ vai escolher N₉ já que é a única opção e P₁ vai perder). Em seguida P₂ escolhe N₄ porque é a única escolha remanescente. P₁ agora escolhe N₅ e P₂ , posteriormente, escolhe N₃ ou N₇. Independentemente da escolha de P₂, P₁ escolhe N₉ e P₂ não tem opções restantes e perde o jogo.

Declaração do problema

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

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

Prova

Geografia generalizada está em PSPACE

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, n_iniciar> onde G é um gráfico direcionado e n_iniciar é o ínicio nó, o algoritmo de M continua da seguinte maneira:

Em M(<G, n_iniciar>):

1. Medir o grau do nó n_iniciar. 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 n_iniciar por uma borda: n₁, n₂, ..., nj.
3. Remova n_iniciar e todas as extremidades ligadas a ele a partir de G para formar G1.
4. Para cada nó n_j na lista n₁, ..., n_i, chamada de M(<G1, nj>).
5. Se todas estas chamadas retornarem aceitar, então não importa que decisão P₁ tome, P₂ tem uma estratégia para vencer, daí retorna rejeitar. Caso contrário (se uma das chamadas retornar rejeitar) P₁ tem uma escolha que vai negar qualquer estratégia bem sucedida para P₂, 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

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 φ = ∃x₁ ∀x₂ ∃x₃ ...Qx_k(ψ) onde Q é ∃ ou ∀. O jogo é jogado por dois jogadores, o P_a e P_e, que alternam na  escolha de valores sucessivos de x_i. P_e ganha o jogo se a fórmula ψ acaba sendo verdadeira, e P_um 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 P₁ é equivalente ao de P_e, e a melhor estratégia para P₂ é 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, P₁ vai primeiro, selecionando a esquerda do nó se x₁ é verdadeiro e o direito nó se x₁ é falso. Cada jogador deve, então, ter turnos forçados e, em seguida, P₂ escolhe um valor para x₂. Estas atribuições se alternando continuam para o lado esquerdo. Depois que ambos os jogadores passam por todos os diamantes, é novamente a vez de P₁, já que partimos do pressuposto de que o último quantificador é existencial. P₁ não tem escolha, a não ser seguir o caminho para o lado direito do gráfico. Em seguida, é a vez de P₂ 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, P_e ganha se ψ é verdadeiro, enquanto que Pa ganha se ψ é falso. O lado direito do grafo garante que P₁ seja vitorioso se, e somente se, P_e vencer, e que P₂ vence se e somente se Pa vencer.

Primeiro vamos mostrar que P₂ sempre ganha quando Pa ganha. Se Pa ganhar, ψ é falso. Se ψ é falso, não existe uma cláusula insatisfatória. P₂ escolherá uma cláusula insatisfatória para ganhar. Em seguida, quando for a vez de P₁, ele deve escolher um literal na cláusula escolhida por P₂. 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 P₂ siga a conexão até o nó correspondente num  diamante da cadeia esquerda, e selecione-a. No entanto, o P₁ agora é incapaz de selecionar um nó adjacente e perde.

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

Consequências

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.

Bibliografia

• 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.