Tiempo polinomial

Tiempo polinomial

En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.

Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N2+N segundos, entonces el problema es resoluble en un "tiempo polinómico".

De esa manera, tiempos de 2n2+5n, o 4n6+7n4-2n2 son polinómicos; pero 2n no lo es.

Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos (log(n)), los lineales (n), los cuadráticos (n2), cúbicos (n3), etc.

Clases de complejidad

En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no-determinista, la clase es llamada NP. Una de las preguntas abiertas más importantes en la actualidad es descubrir si estas clases son diferentes o no. El Clay Mathematics Institute ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.

Diagrama de clases de complejidad. Si P = NP, P contendría las zonas NP y NP-completo.

Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P (Ver NP-completo para una definición precisa). Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP-completo tendrían intersección vacía.

La importancia de la pregunta P = NP radica en que de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo polinómico.


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Tiempo polinomial incremental — En complejidad computacional, el tiempo polinomial incremental (en inglés incremental polynomial delay) se refiere a cuando el tiempo de ejecución de un algoritmo de enumeración de un conjunto es polinomial en términos de la entrada y de los… …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

  • Problema de la suma de subconjuntos — Saltar a navegación, búsqueda El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea… …   Wikipedia Español

  • P (Complejidad computacional) — Saltar a navegación, búsqueda Contenido 1 Introducción 2 La clase P 3 Problemas notables en P 4 Propiedades …   Wikipedia Español

  • P (clase de complejidad) — Se ha sugerido que este artículo o sección sea fusionado con Tiempo polinómico (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí …   Wikipedia Español

  • 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

  • EXPTIME — En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una… …   Wikipedia Español

  • Teoría de la complejidad computacional — 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

  • Algoritmo de aproximación — En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP hard; como es poco… …   Wikipedia Español

Compartir el artículo y extractos

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