Diferencia entre revisiones de «PSPACE-completo»
Contenido eliminado Contenido añadido
m Mantenimiento de Control de autoridades |
Etiqueta: editor de código 2017 |
||
Línea 30:
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|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.
Línea 37:
** Se finaliza si se aceptan todas, en otro caso continúa el proceso.
Consumo Espacial: El número de niveles de la recursión será igual al número de nodos de G. La cantidad de información almacenada en cada nivel es también igual al número de nodos de G. Por lo tanto el consumo total del espacio es lineal.
== Enlaces externos ==
| |||