NSPACE
En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no-determinista de DSPACE.
La clase de complejidad NPSPACE se puede definir a partir de NSPACE como:
- <math>\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)</math>
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
El contenido de esta página, es sólo un esbozo de artículo sobre matemática. Ampliándolo ayudarás a mejorar Wikipedia.
Puedes ayudarte con las wikipedias en otras lenguas. También puedes ayudar cambiando este cartel por uno más específico.
Categorías
Wikipedia:Esbozo matemática | Clases de complejidad