En matemáticas y ciencias de la computación , un juego de guijarros es un tipo de juego matemático que se juega colocando "guijarros" o "marcadores" en un gráfico acíclico dirigido de acuerdo con ciertas reglas:
La solución trivial es construir un grafo de n vértices en n pasos usando n guijarros. Hopcroft, Paul y Valiant [1] demostraron que cualquier vértice de un grafo de n vértices puede construirse con O( n /log n ) guijarros 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 todos los f construibles en el tiempo . Lipton y Tarjan [2] demostraron que cualquier grafo dirigido acíclico planar de n vértices con un grado de entrada máximo k puede construirse usando O( √ n + k log 2 n ) guijarros. También demostraron que es posible obtener una reducción sustancial en guijarros mientras se preserva un límite polinomial en el número de pasos de guijarro con un teorema de que cualquier grafo dirigido acíclico planar de n -vértices con máximo grado de entrada k puede ser guijarro usando O( n 2/3 + k ) guijarros en tiempo O( n 5/3 ). Alon, Seymour y Thomas [3] demostraron que cualquier grafo dirigido acíclico de n -vértices sin k h - menor y con máximo grado de entrada k puede ser guijarro usando O( h 3/2 n 1/2 + k log n ) guijarros.
Stephen Cook y Ravi Sethi desarrollaron una extensión de este juego, conocida como "black-white pebbling" (guijarros blancos y negros), en un artículo de 1976. [4] También agrega guijarros blancos, que pueden colocarse en cualquier vértice a voluntad, pero solo pueden eliminarse si todos los vértices ancestros inmediatos del vértice también están empedrados. El objetivo sigue siendo colocar un guijarro negro en el vértice objetivo, pero el empedrado de los vértices adyacentes puede realizarse con guijarros de cualquier color.
Takumi Kasai et al. desarrollaron un juego en el que una piedra puede moverse a lo largo de una flecha de borde hasta un vértice desocupado solo si una segunda piedra se encuentra en un tercer vértice de control; el objetivo es mover una piedra hasta un vértice objetivo. Esta variación convierte al juego de piedras en una generalización de juegos como las damas chinas y Halma . Determinaron la complejidad computacional de las versiones de este juego para un jugador y para dos jugadores, y casos especiales de las mismas. En la versión para dos jugadores, los jugadores se turnan para mover las piedras. También puede haber restricciones sobre qué piedras puede mover un jugador. [5]
El pebbling se puede utilizar para extender los juegos de Ehrenfeucht-Fraïssé . [6]