Existe uma redução nos jogos de “porta e pressão” que não explode o comprimento da solução?

12

Este artigo prova que, em um jogo com portas e placas de pressão, é difícil para o PSPACE determinar se o avatar (do jogador) pode ou não alcançar um determinado local. Isso é comprovado por uma redução do TQBF , e o comprimento das soluções resultantes depende exponencialmente do número de quantificadores universais na fórmula.

Existe uma redução de uma máquina NPSPACE para um jogo em que a duração das soluções do jogo está polinomialmente relacionada à duração dos caminhos de aceitação da máquina?

Jeffε
fonte
1
breve esboço de uma definição mais formal de "jogo com portas e placas de pressão" [infelizmente, não é realmente apresentado no jornal em um só lugar]. o jogo generalizado é um mapa 2D infinito que pode ser representado como um gráfico (de tamanho arbitrário) dos espaços / regiões conectados. os nós do gráfico são espaços / regiões (equiv, células / túneis etc.), arestas são portas entre eles. as placas de pressão são interruptores contidos nos espaços. um interruptor controla a abertura da porta. as portas começam em um estado arbitrário, talvez algumas abertas, outras fechadas. (etc.) ... no entanto, parece que o autor está considerando apenas gráficos planares.
vzn
além disso, a questão parece estar próxima, ou quase equivalente, da questão de saber se o comprimento do caminho mínimo de uma solução (contada nas arestas) através do gráfico está polinomial ou exponencialmente relacionado ao tamanho do gráfico / comutadores. .. este por sua vez parece estar estreitamente relacionado com a questão de como muitos ciclos no caminho são necessárias ou se eles não são ...
vzn

Respostas:

2

Talvez você possa simular facilmente um LBA; A ideia é a seguinte:

  • para cada célula da fita LBA, adicione um gadget de célula que possa ser inserido apenas a partir da parte inferior e com saída somente a partir da parte superior;Gi

  • o dispositivo possui uma porta de entrada que simula a posição da cabeça (apenas um é aberto a cada passo);C iCiCi

  • então há portas de dois bits e ; é aberto se a célula contiver um zero, é aberto se houver célula que contenha um;O i Z i O iZiOiZiOi

  • as duas portas bit conduzem a uma estrutura de controle semelhante, feita por vários corredores de mão única ; um corredor corresponde a um estado do LBA, e a porta do corredor é aberta se e somente se o estado atual do LBA for ; i q iqiiqi

  • de acordo com a tabela de transição (possivelmente não determinística) do LBA, uma travessia do corredor (aberto) altera o estado atual do LBA e a configuração das portas de bit, fecha a porta e abre ou .C i + 1 C i - 1CiCi+1Ci1

Um gadget de célula é esboçado na figura abaixo.

insira a descrição da imagem aqui

Escolhas não determinísticas podem ser realizadas dividindo os corredores nas estruturas de controle em dois ou mais sub corredores, como mostrado na figura abaixo.

insira a descrição da imagem aqui

Nota: se uma placa puder apenas abrir / fechar uma porta, você poderá adicionar uma estrutura auxiliar com (longos) corredores de sentido único que (des) ativam as portas de estado distintas de cada célula.

Marzio De Biasi
fonte
Se uma porta puder ser aberta apenas por uma única placa e só puder ser fechada por uma única placa, você poderá usar dispositivos de cruzamento (que eu poderia descrever) para permitir que os corredores conduzam apenas à entrada da célula desejada (que remove o necessário para as portas C1), implemente Z1 e O1 com muitas portas diferentes, cada uma com uma placa de fechamento imediatamente depois e implementando as portas q0, ..., q4 como minicorredores com duas portas seguidas por uma placa que fecha uma dessas duas portas e uma placa que fecha um dos pares de portas abertas no qi do outro [valor da célula].
Independentemente das sugestões do meu comentário anterior, se o LBA for não determinístico, os corredores unidirecionais precisariam de sub corredores, para indicar a escolha não determinística.
?? não é reconhecimento LBA = (N) PSPACE? parece que seria mais útil se a resposta fosse formulada em termos de uma classe de complexidade.
vzn
@ RickyDemer: ok, adicionei um exemplo de uma escolha não determinística. Você está usando os meta-temas de Viglietta para provar a complexidade de alguns jogos?
Marzio De Biasi
Eu estava lendo seus metateoremas e percebi que isso é uma coisa que eles não abordam.
2

Outra maneira rápida de provar o metateorema 2c (dureza PSPACE quando as portas são controladas por duas placas) é usar a estrutura da lógica de restrições não determinísticas ( RA Hearn e ED Demaine, o modelo de computação da lógica de restrições não determinísticas: reduções e aplicações ).

Neste caso, é suficiente usar uma série horizontal de pares de corredores verticais. O estado de cada par de corredores representa a direção (interna / externa) de uma aresta no gráfico de restrição original. É suficiente simular o gadget AND e OR, como esboçado na figura abaixo.

insira a descrição da imagem aqui

Marzio De Biasi
fonte
-5

esse tipo de pesquisa de relacionar videogames à complexidade computacional é bastante intrigante, mas também é bastante novo, geralmente com menos de uma década. Argumentarei aqui que há uma sutileza que às vezes está sendo perdida nas análises atuais [não vi / notei isso apontado no artigo citado ou em outros artigos até agora] e que impede responder definitivamente à pergunta declarada.

para provar uma relação com um sistema computacional, é preciso ser capaz de mapear o sistema computacional para o jogo e vice-versa. por exemplo, no artigo citado por Viglietta acima, existe um conceito de que placas e portas de pressão (isto é, as portas de controle das placas de pressão) podem ser "como" QBFs. essa analogia é certamente viável, pois eles a mapearam. pode-se usar um QBF para resolver um jogo com placas e portas de pressão.

no entanto, aqui está a sutileza. em um determinado jogo, os layouts do jogo são basicamente fixos. no design de videogames, o conceito de diferentes layouts é chamado de "layout design" e não é um "dado" de todos os jogos. por exemplo, no inovador jogo Doom, as ferramentas de design de níveis eram de código aberto, ou seja, disponibilizadas para os jogadores usarem. em outras palavras, o design de nível arbitrário pode ser considerado parte do jogo. mas em outros jogos considerados nos jornais, os videogames, como originalmente criados, têm níveis fixos. os jornais às vezes não estão explicitamente levando isso em consideração.

portanto, existe um forte argumento de que na maioria dos jogos sem design de níveis ou layouts aleatórios, os níveis são fixos, e isso tem um grande impacto na complexidade real da solução do "jogo". ou seja, o que exatamente é o "jogo"? inclui layouts aleatórios e / ou possibilidade de criação de níveis? o design de nível faz parte do mapeamento computacional? essas questões são encobertas um pouco nos documentos atuais.

Levado ao extremo oposto dos artigos, alguém poderia argumentar que todas as implementações reais de videogame são solucionáveis ​​pelos FSMs porque possuem memória finita !

para que haja mapeamentos computacionais reais, basicamente é preciso generalizar o jogo para envolver

  • níveis com tamanho arbitrário! para que isso possa ser mapeado para TMs com fitas de "entrada" arbitrárias / ilimitadas.
  • design de níveis que permite a criação desses níveis.

um problema de mapeamento ligeiramente semelhante surge na pesquisa do CA / Cellular Automata, onde há idéias sobre o uso de padrões periódicos infinitos nas CAs como "padrões iniciais" para provar a equivalência / completude da MT.

portanto, em geral, sua pergunta não é estritamente definida até que você esclareça melhor (ou seja, defina formalmente / matematicamente ) o que você quer dizer com "em um jogo com portas e placas de pressão" e de uma maneira que mesmo o jornal aparentemente não defina estritamente, especialmente escrever idéias sobre design de níveis, níveis ilimitados de tamanho, etc. mas observe que os "jogos" definidos com esses recursos foram abstraídos dos videogames reais / reais de uma maneira muito significativa.

então, em suma, acho que essa é uma pesquisa interessante / interessante, mesmo que iniciando como algo informal e mereça mais avanços, mas, até certo ponto, sua formalização deve ser mais rigorosa, especialmente nas definições básicas, se quiser avançar mais. deve fazer uma distinção mais estrita / formal / transparente entre as implementações e as abstrações .

vzn
fonte
por exemplo, aqui está um artigo sobre Battleship como NP completo, mas melhor / formalmente declara / descreve a generalização completa de NP do jogo de tamanho limitado. Battleships como um problema de decisão por Sevenster, sec2.
vzn
outro exemplo de sutileza na generalização / abstração do problema, a generalização da geometria de 15 quebra-cabeças pode afetar sua integridade NP . observe que uma grade quadrada versus retangular pode afetar os resultados.
vzn
7
Embora isso seja um problema, acho que sua afirmação de que isso é encoberto na literatura é muito exagerada. E dada a existência de artigos como Fraenkel e cols. FOCS 1978 sobre a complexidade das peças de damas, Even e Tarjan JACM 1976 na Hex e Robertson e Munro Util. Matemática. 1978, no Instant Insanity, sua afirmação de que essa é uma área totalmente nova também é muito exagerada.
David Eppstein
obviamente, os jogos em geral estudados a partir de uma exibição do TCS não são novos, são os seus videogames , como o texto é cuidadoso ao declarar.
vzn
1
Paciência Mahjong : 1994. Campo Minado : 2000. Tetris : 2002. Eles não contam como videogames ou você usa uma longa década ?
Peter Shor