Roadblock problem

(Veja o livro de Harel, p.184.)

Imagine um grafo cada uma de cujas arestas tem uma de três cores: vermelho, azul ou amarelo. Alguns vértices do grafo são pretos, outros são brancos, e outros não têm cor alguma.

Há dois jogadores, Preto e Branco. Cada jogador tem um certo número de fichas: Preto tem fichas pretas e Branco tem fichas brancas. Cada ficha está estacionada sobre algum vértice e há no máximo 1 ficha em cada vértice.

Os dois jogadores se alternam movimentando suas fichas de acordo com a seguinte regra:  em cada jogada, um jogador move uma de suas fichas para um novo vértice ao longo de um caminho monocromático cujos vértices estejam livres de quaisquer fichas.  O primeiro jogador a atingir um vértice que tenha a sua cor é declarado vencedor.

O problema da barreira (roadblock problem) consiste no seguinte:  dada uma configuração do jogo (ou seja, um grafo como o descrito acima, com fichas estacionadas nos vértices), decidir se existe uma estratégia vencedora para o próximo jogador a jogar.

Não existe algoritmo polinomial que resolva o problema. A complexidade do problema é exponencial.

Valid HTML 4.01 Strict Valid CSS!