Diferencia entre revisiones de «UP (clase de complejidad)»
Contenido eliminado Contenido añadido
m Corrección de enlace |
m Enlace corregido |
||
| Línea 2: | Línea 2: | ||
Un lenguaje ''L'' pertenece a UP si existe un algortimo ''A'' de tiempo polinómico con dos entradas y una constante ''c'' tal que: |
Un lenguaje ''L'' pertenece a UP si existe un algortimo ''A'' de tiempo polinómico con dos entradas y una constante ''c'' tal que: |
||
:L = {x in {0,1}* | ∃! valor, y con |y| = O(|x|<sup>c</sup>) tal que A(x,y) = 1} |
:L = {x in {0,1}* | ∃! valor, y con |y| = [[Cota superior asintótica|O]](|x|<sup>c</sup>) tal que A(x,y) = 1} |
||
{{Clases de complejidad}} |
{{Clases de complejidad}} |
||
Revisión del 08:54 14 sep 2004
En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no-determinístico, no-ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no-determinística tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas.
Un lenguaje L pertenece a UP si existe un algortimo A de tiempo polinómico con dos entradas y una constante c tal que:
- L = {x in {0,1}* | ∃! valor, y con |y| = O(|x|c) tal que A(x,y) = 1}