DTIME
En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
La clase de complejidad P se puede definir a partir de DTIME como:
- <math>\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(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