UP (complejidad)

UP (complejidad)

UP (complejidad)

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}
Obtenido de "UP (complejidad)"

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Complejidad computacional — Saltar a navegación, búsqueda La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos… …   Wikipedia Español

  • Complejidad (álbum) — Complejidad Álbum de Efecto Mariposa Publicación 24 de mayo de 2005 Grabación Madrid …   Wikipedia Español

  • Complejidad social — Saltar a navegación, búsqueda Complejidad social El segundo camino que ha tomado la naturaleza para formar sociedades complejas es el de desarrollar una especie con suficiente inteligencia como para pasar sus conocimientos a las generaciones… …   Wikipedia Español

  • complejidad — ‘Cualidad de complejo’: «No negaba la complejidad del problema» (Belli Mujer [Nic. 1992]). Es preferible a complexidad, voz poco usada, pero que parece estar recuperando cierta vigencia, especialmente en algunas zonas de América, por influencia… …   Diccionario panhispánico de dudas

  • complejidad — sustantivo femenino 1. (no contable) Característica de complejo: Dada la complejidad del problema, habrá que examinarlo detenidamente …   Diccionario Salamanca de la Lengua Española

  • complejidad — o complexidad sustantivo femenino complicación. * * * Sinónimos: ■ dificultad, complicación, confusión, laberinto, embrollo, lío, diversidad …   Diccionario de sinónimos y antónimos

  • complejidad — f. Cualidad de complejo …   Diccionario de la lengua española

  • Complejidad biológica — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Complejidad ciclomática — La Complejidad Ciclomática (en inglés, Cyclomatic Complexity) es una métrica del software que proporciona una medición cuantitativa de la complejidad lógica de un programa. Es una de las métricas de software de mayor aceptación, ya que ha sido… …   Wikipedia Español

  • Complejidad irreducible — Existen desacuerdos sobre la neutralidad en el punto de vista de la versión actual de este artículo o sección. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Complejidad en los juegos — Este artículo o sección sobre ocio necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 11 de junio de 2008. También puedes ayudar… …   Wikipedia Español

Compartir el artículo y extractos

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