Diferencia entre revisiones de «PSPACE-completo»
Contenido eliminado Contenido añadido
mSin resumen de edición |
mSin resumen de edición |
||
Línea 29:
Véase [[Complejidad en los juegos]] para más juegos cuya completitud para PSPACE o cualquier otra clase de complejidad ha sido probada.
===Geografía Generalizada===
El problema de la Geografía Generalizada es un juego infantil similar a las palabras encadenadas pero empleando únicamente ciudades que deban empezar con el nombre de la anterior sin repetir ninguna. Con los datos de este problema podemos construir el grafo <G,b> del conjunto de ciudades relacionado por su letra inicial-final:
*Con entrada <G,b>:
**Si b no tiene aristas salientes, se rechaza.
| |||