# 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$_1$ para o nó N$_2$ se, e somente se, a cidade com rotulagem N$_2$ começa com a letra que termina o nome da cidade com rotulagem N$_1$. 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$_1$ como o jogador que se move de primeira e P$_2$ como o jogador de segundo e nomeamos os nós de N$_1$ a N$_n$. Na figura acima, P$_1$ tem uma estratégia vencedora, conforme segue: N$_1$ aponta apenas para os nós de N$_2$ e N$_3$. Assim, o primeiro movimento de P$_1$ deve ser uma dessas duas opções. P$_1$ escolhe N$_2$ (se P$_1$ escolher N$_3$, P$_2$ vai escolher N$_9$ já que é a única opção e P$_1$ vai perder). Em seguida P$_2$ escolhe N$_4$ porque é a única escolha remanescente. P$_1$ agora escolhe N$_5$ e P$_2$ , posteriormente, escolhe N$_3$ ou N$_7$. Independentemente da escolha de P$_2$, P$_1$ escolhe N$_9$ e P$_2$ 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$_1$ 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}$>):
* 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.
* Construir uma lista de todos os nós, acessível a partir de n$_{iniciar}$ por uma borda: n$_1$, n$_2$, ..., nj.
* Remova n$_{iniciar}$ e todas as extremidades ligadas a ele a partir de G para formar G1.
* Para cada nó n$_j$ na lista n$_1$, ..., n$_i$, chamada de M(<G1, nj>).
* Se todas estas chamadas retornarem aceitar, então não importa que decisão P$_1$ tome, P$_2$ tem uma estratégia para vencer, daí retorna rejeitar. Caso contrário (se uma das chamadas retornar rejeitar) P$_1$ tem uma escolha que vai negar qualquer estratégia bem sucedida para P$_2$, 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$_1$ ∀x$_2$ ∃x$_3$ ...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$_1$ é equivalente ao de P$_e$, e a melhor estratégia para P$_2$ é 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$_1$ vai primeiro, selecionando a esquerda do nó se x$_1$ é verdadeiro e o direito nó se x$_1$ é falso. Cada jogador deve, então, ter turnos forçados e, em seguida, P$_2$ escolhe um valor para x$_2$. 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$_1$, já que partimos do pressuposto de que o último quantificador é existencial. P$_1$ não tem escolha, a não ser seguir o caminho para o lado direito do gráfico. Em seguida, é a vez de P$_2$ 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$_1$ seja vitorioso se, e somente se, P$_e$ vencer, e que P$_2$ vence se e somente se Pa vencer.
Primeiro vamos mostrar que P$_2$ sempre ganha quando Pa ganha. Se Pa ganhar, ψ é falso. Se ψ é falso, não existe uma cláusula insatisfatória. P$_2$ escolherá uma cláusula insatisfatória para ganhar. Em seguida, quando for a vez de P$_1$, ele deve escolher um literal na cláusula escolhida por P$_2$. 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$_2$ siga a conexão até o nó correspondente num diamante da cadeia esquerda, e selecione-a. No entanto, o P$_1$ agora é incapaz de selecionar um nó adjacente e perde.
Agora vamos mostrar que P$_1$ 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$_2$ pode escolher qualquer cláusula. Então P$_1$ escolhe o literal que é verdadeiro. E porque ele é verdadeiro, o seu nó adjacente na vertical esquerda já foi selecionado, então P$_2$ 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.