NPSPACE

NPSPACE

En teoría de la complejidad computacional, la clase de complejidad NPSPACE 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, NPSPACE = PSPACE.


Wikimedia foundation. 2010.

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

Mira otros diccionarios:

  • NPSPACE — In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. Nach dem Satz von Savitch ist PSPACE gleich der Klasse NPSPACE, der… …   Deutsch Wikipedia

  • NPSPACE — …   Википедия

  • Класс NPSPACE — Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства 2 Классы PSPACE, NPSPACE 3 PSPACE полные языки …   Википедия

  • Classe NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Classe de complexité — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Classes de complexité P et NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexite P — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexite algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexité Algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexité des algorithmes — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

Compartir el artículo y extractos

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