Diferencia entre revisiones de «UP (clase de complejidad)»
Contenido eliminado Contenido añadido
m Robot: Removing template: Clases de complejidad |
m miniesbozo: matemáticas usando monobook-suite |
||
| Línea 1: | Línea 1: | ||
En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]] '''UP''' (tiempo polinómico, no-determinista, no-ambiguo) es el conjunto de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos en [[tiempo polinómico]] por una [[máquina de Turing]] no-determinista tal que la solución si existe es única. La clase UP está contenida en [[NP]] y contiene a [[tiempo polinómico|P]]. No se sabe si estas inclusiones son estrictas. |
{{miniesbozo|matemáticas}}En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]] '''UP''' (tiempo polinómico, no-determinista, no-ambiguo) es el conjunto de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos en [[tiempo polinómico]] por una [[máquina de Turing]] no-determinista tal que la solución si existe es única. La clase UP está contenida en [[NP]] y contiene a [[tiempo polinómico|P]]. No se sabe si estas inclusiones son estrictas. |
||
Un lenguaje ''L'' pertenece a UP si existe un algoritmo ''A'' de tiempo polinómico con dos entradas y una constante ''c'' tal que: |
Un lenguaje ''L'' pertenece a UP si existe un algoritmo ''A'' de tiempo polinómico con dos entradas y una constante ''c'' tal que: |
||
Revisión del 23:09 14 mar 2008
La plantilla {{Esbozo}} está obsoleta tras una consulta de borrado, no se debe usar.En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no-determinista, 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-determinista 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 algoritmo 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}