ESPACIONP

ESPACIONP

ESPACIONP

En teoría de la complejidad computacional, la clase de complejidad ESPACIONP (NPSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio polinómico y tiempo ilimitado.

Por el teorema de Savitch, ESPACIONP = ESPACIOP.

Obtenido de "ESPACIONP"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • ESPACIONP — En teoría de la complejidad computacional, la clase de complejidad ESPACIONP (NPSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio polinómico y tiempo… …   Enciclopedia Universal

  • Clases de complejidad — Anexo:Clases de complejidad Saltar a navegación, búsqueda Esta es la lista de clases de complejidad en teoría de la complejidad computacional. Muchas de estas clases tienen una co clase que contiene los problemas complementarios a los de la clase …   Wikipedia Español

  • ESPACIOP — En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial y tiempo ilimitado. La definición no …   Enciclopedia Universal

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”