juego de guijarros

En matemáticas e informática , un juego de guijarros es un tipo de juego matemático que consiste en colocar "guijarros" o "marcadores" en un grafo dirigido acíclico según ciertas reglas:

• Un paso determinado del juego consiste en colocar una piedrecita en un vértice vacío o en quitar una piedrecita de un vértice que ya tenía una piedrecita.
• Un vértice solo puede estar cubierto de guijarros si todos sus predecesores están cubiertos de guijarros.
• El objetivo del juego es colocar sucesivamente una piedrecita en cada vértice de G (en cualquier orden) minimizando al mismo tiempo el número de piedrecitas que se encuentran simultáneamente en el grafo.

La solución trivial es llenar un grafo de n vértices en n pasos usando n piedras. Hopcroft, Paul y Valiant ^{[ 1 ]} demostraron que cualquier vértice de un grafo de n vértices puede llenarse con O( n /log n ) piedras donde la constante depende del grado de entrada máximo. Esto les permitió demostrar que DTIME ( f ( n )) está contenido en DSPACE ( f ( n )/log f ( n )) para todo f construible en tiempo . Lipton y Tarjan ^{[ 2 ]} demostraron que cualquier grafo dirigido acíclico planar de n vértices con grado de entrada máximo k puede llenarse usando O( √ n + k log ₂ n ) piedras. También demostraron que es posible obtener una reducción sustancial en guijarros mientras se preserva una cota polinómica en el número de pasos de guijarros con un teorema que cualquier grafo dirigido acíclico planar de n vértices con grado de entrada máximo k puede ser guijarrado usando O( n ^2/3 + k ) guijarros en O( n ^5/3 ) tiempo. Alon, Seymour y Thomas ^{[ 3 ]} demostraron que cualquier grafo dirigido acíclico de n vértices sin k _h -menor y con grado de entrada máximo k puede ser guijarrado usando O( h ^3/2 n ^1/2 + k log n ) guijarros.       

Una extensión de este juego, conocida como "pincelado blanco-negro", fue desarrollada por Stephen Cook y Ravi Sethi en un artículo de 1976. ^{[ 4 ]} También añade guijarros blancos, que pueden colocarse en cualquier vértice a voluntad, pero solo pueden retirarse si todos los vértices ancestros inmediatos del vértice también están cubiertos de guijarros. El objetivo sigue siendo colocar un guijarro negro en el vértice objetivo, pero el taponado de vértices adyacentes puede hacerse con guijarros de cualquier color.

Takumi Kasai y colaboradores desarrollaron un juego en el que una ficha puede moverse a lo largo de una flecha de borde hacia un vértice desocupado solo si una segunda ficha se encuentra en un tercer vértice de control; el objetivo es mover una ficha a un vértice objetivo. Esta variación convierte el juego de las fichas en una generalización de juegos como las damas chinas y Halma . Determinaron la complejidad computacional de las versiones para uno y dos jugadores de este juego, así como casos especiales. En la versión para dos jugadores, los jugadores se turnan para mover las fichas. También puede haber restricciones sobre qué fichas puede mover un jugador. ^{[ 5 ]}

El pebbling puede utilizarse para extender los juegos de Ehrenfeucht–Fraïssé . ^{[ 6 ]}

• Juego de repujas en grafos : Se distribuyen varias piedras entre los vértices de un grafo no dirigido; el objetivo es mover al menos una a un vértice específico. Pero para mover una piedra a un vértice adyacente, hay que descartar otra piedra que se encuentre en el mismo vértice.
• Juego de lanzar fichas
• Teorema del separador planar

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en Ciencias de la Computación Teórica. Una serie de EATCS. ​​Berlín: Springer-Verlag . ISBN 978-3-540-00428-8. Zbl 1133.03001 . 
• Nicholas Pippenger . Pebbling. Informe técnico RC 8258, Centro de Investigación IBM Watson , 1980. Publicado en las Actas del 5.º Simposio IBM sobre Fundamentos Matemáticos de la Informática, Japón .
• Jakob Nordström . Juegos de guijarros, complejidad de las pruebas y compensaciones espacio-temporales. Métodos lógicos en informática , volumen 9, número 3, artículo 15, septiembre de 2013.