Complejidad temporal del algoritmo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de junio de 2022; las comprobaciones requieren 3 ediciones .

En informática , la complejidad temporal de un algoritmo se define como una función de la longitud de la cadena que representa la entrada, igual al tiempo de ejecución del algoritmo en la entrada dada [1] . La complejidad temporal de un algoritmo generalmente se expresa utilizando la notación "O" grande , que tiene en cuenta solo el término de orden más alto y tampoco tiene en cuenta los factores constantes, es decir, los coeficientes. Si la complejidad se expresa de esta forma, se habla de una descripción asintótica de la complejidad temporal, es decir, como el tamaño de la entrada tiende a infinito. Por ejemplo, si existe un número tal que el tiempo de ejecución del algoritmo para todas las entradas de longitud no exceda , entonces la complejidad temporal de este algoritmo se puede estimar asintóticamente como . $n_ {0}$ $n>n_{0}$ ${\ estilo de visualización 5n^{3}+3n}$ $O(n^{3})$

La complejidad del tiempo generalmente se estima contando el número de operaciones elementales realizadas por el algoritmo. El tiempo de ejecución de una de estas operaciones se toma como una constante, es decir, se estima asintóticamente como . En tal notación, el tiempo total de ejecución y el número de operaciones elementales realizadas por el algoritmo difieren en un máximo de un factor constante, que no se tiene en cuenta en la notación O. Dado que el tiempo de ejecución del algoritmo puede diferir en entradas del mismo tamaño, generalmente se usa el tiempo de ejecución del peor de los casos , que se denota y define como el tiempo de ejecución más largo del algoritmo en todas las longitudes de entrada . Con menos frecuencia, y esto suele especificarse específicamente, se calcula la complejidad promedio , es decir, la expectativa matemática del tiempo de ejecución para todas las entradas posibles. El tiempo de ejecución de un algoritmo se puede clasificar según la función que esté bajo notación O. Por ejemplo, un algoritmo con se llama algoritmo con tiempo de ejecución lineal , y un algoritmo con para algunos se llama polinomio . $O(1)$ $Tennesse)$ $norte$ ${\ estilo de visualización T (n) \ en O (n)}$ $T(n)\in O(n^{\alpha })$ $\ alfa > 1$

Tabla de tiempos de dificultad

La siguiente tabla resume las clases de complejidad más comunes . En la tabla , denota un polinomio arbitrario en , es decir, . ${\ estilo de visualización poli (x)}$ $X$ ${\ Displaystyle poli(x)=x^{O(1)))$

Nombre	Clase de dificultad	Horas Laborales, $Tennesse)$	Ejemplos de tiempo de trabajo	Ejemplos de algoritmos
tiempo constante		$O(1)$	$diez$	Determinación de la paridad de un número entero (representado en binario)
función inversa de Ackermann		${\ estilo de visualización O (\ alfa (n))}$		Análisis de amortización por operación mediante conjuntos disjuntos
tiempo logarítmico iterado		$O(\log ^{*}n)$		Coloraciones de ciclo distribuido
doblemente logarítmico		${\ estilo de visualización O (\ log \ log n)}$		Tiempo de amortización por operación al usar cola de prioridad limitada [2]
tiempo logarítmico	DLOGTIME	$O(\log n)$	$\log n$ , $\log n^{2}$	Búsqueda binaria
tiempo polilogarítmico		$poly(\log n)$	${\displaystyle (\log n)^{2))$
tiempo sublineal		${\ estilo de visualización O (n ^ {c})}$ a ${\ estilo de visualización 0 <c <1}$	${\ estilo de visualización n^{1/2}}$ , ${\ estilo de visualización n^{2/3}}$	Buscar en un árbol k-dimensional
tiempo lineal		$En)$	$norte$	Encontrar el elemento más pequeño o más grande en una matriz no ordenada
"n log-asterisco n"		$O(n\log ^{*}n)$		Algoritmo de triangulación de polígonos de Seidel .
tiempo logarítmico lineal		$O(n\log n)$	${\ estilo de visualización n \ registro n}$ , ${\ estilo de visualización \ iniciar sesión!}$	Clasificación de comparación más rápida
tiempo cuadrático		$O(n^{2})$	$n^{2}$	Clasificación por burbuja , clasificación por inserción , plegado recto
tiempo cubico		$O(n^{3})$	$n ^ 3$	La multiplicación habitual de dos matrices. Cálculo de correlación parcial . $n\veces n$
tiempo polinomial	PAGS	$2^{O(\log n)}=poli(n)$	$norte$ . . ${\ estilo de visualización n \ registro n}$ ${\ estilo de visualización n^{10))$	Algoritmo de Karmarkar para programación lineal , prueba de simplicidad AKS
tiempo cuasi-polinomio	QP	${\displaystyle 2^{poli(\log n)))$	${\ estilo de visualización n^{\ registro \ registro n))$ , ${\ Displaystyle n ^ {\ log n}}$	El más rápido conocido es el algoritmo de aproximación para el problema de Steiner orientado . $O(\registro^{2}n)$
tiempo subexponencial (primera definición)	SUBEXP	$O(2^{n^{\varepsilon)))$ para todos $\varepsilon >0$	$2^{\log n^{\log \log n))$	Asumiendo hipótesis teóricas, BPP está contenido en SUBEXP. [3]
tiempo subexponencial (segunda definición)		${\ estilo de visualización 2 ^ {o (n)}}$	${\ estilo de visualización 2 ^ {n ^ {1/3}}}$	Los algoritmos más rápidos conocidos para factorizar enteros y verificar el isomorfismo de gráficos
tiempo exponencial (con exponente lineal)	mi	${\ estilo de visualización 2 ^ {O (n)}}$	${\ estilo de visualización 1.1^{n}}$ , $10^{n}$	Resolviendo el problema del viajante de comercio con programación dinámica
tiempo exponencial	EXPTIME	${\displaystyle 2^{poli(n)))$	$2^{{n}}$ , ${\ estilo de visualización 2 ^ {n ^ {2}}}$	Resolviendo el problema del orden de multiplicación de matrices usando enumeración exhaustiva
tiempo factorial		${\ estilo de visualización O (n!)}$	$¡norte!$	Resolviendo el problema del viajante de comercio mediante búsqueda exhaustiva
tiempo doblemente exponencial	2-EXPTIM	$2^{2^{poli(n)))$	$2^{{2^{n}}}$	Comprobación de la corrección de una declaración dada en la aritmética de Presburger
		${\sqrt[{n}]{\log _{n}(n)))$	1 para n >= 1

Tiempo constante

Se dice que un algoritmo es un algoritmo de tiempo constante (escrito como tiempo ) si el valor está limitado a un valor independiente del tamaño de la entrada. Por ejemplo, obtener un solo elemento en una matriz lleva un tiempo constante porque se ejecuta un solo comando para encontrarlo. Sin embargo, encontrar el valor mínimo en una matriz no ordenada no es una operación de tiempo constante porque tenemos que observar cada elemento de la matriz. Por lo tanto, esta operación toma un tiempo lineal, . Si el número de elementos se conoce de antemano y no cambia, dicho algoritmo puede denominarse algoritmo de tiempo constante. $O(1)$ $Tennesse)$ $En)$

A pesar del nombre "tiempo constante", el tiempo de ejecución no tiene por qué ser independiente del tamaño de la tarea, pero sí un límite superior en el tiempo de ejecución. Por ejemplo, el problema de "intercambiar los valores de y , si es necesario, para obtener el resultado " se considera un problema de tiempo constante, aunque el tiempo de ejecución del algoritmo puede depender de si la desigualdad ya se cumple o no. Sin embargo, existe alguna constante por la cual el tiempo de ejecución de la tarea nunca excede . $a$ $b$ ${\ estilo de visualización a \ leq b}$ ${\ estilo de visualización a \ leq b}$ $t$ $t$

A continuación se muestra un ejemplo de código que se ejecuta en tiempo constante:

índice int = 5; elemento int = lista[índice]; si (la condición es verdadera) entonces realizar algunas operaciones con tiempo de ejecución constante más realizar algunas operaciones con tiempo de ejecución constante para i = 1 a 100 para j = 1 a 200 realizar algunas operaciones con tiempo de ejecución constante

Si es igual a , donde es una constante, entonces esto es equivalente a igual a . $Tennesse)$ ${\ estilo de visualización O (\ alfa)}$ $\alfa$ $Tennesse)$ $O(1)$

Tiempo logarítmico

Se dice que un algoritmo se ejecuta en tiempo logarítmico si . Dado que las computadoras usan el sistema numérico binario , la base del logaritmo es (es decir, ). Sin embargo, al cambiar la base del logaritmo y difieren solo por un factor constante , que se descarta en la notación O-grande. Por lo tanto, es la notación estándar para los algoritmos de tiempo logarítmico, independientemente de la base del logaritmo. $T(n)=O(\log n)$ $2$ $\ log _ {2} n$ ${\ estilo de visualización \ registro _ {a} n}$ ${\ estilo de visualización \ registro _ {b} n}$ $\ log_b un$ $O(\log n)$

Los algoritmos que se ejecutan en tiempo logarítmico se encuentran comúnmente en operaciones en árboles binarios o cuando se utiliza la búsqueda binaria .

$O(\log n)$ los algoritmos para trabajar con matrices de datos de tamaño se consideran altamente eficientes, ya que la relación entre el tiempo de ejecución de una operación y el tamaño de la matriz disminuye al aumentar este tamaño. $norte$

Un ejemplo muy simple de tal algoritmo es buscar palabras en un diccionario. Considere un diccionario que contiene palabras ordenadas alfabéticamente. Al mismo tiempo, suponemos que todas las palabras tienen longitud y que podemos acceder a cualquier elemento del diccionario por índice en tiempo constante. Sea el -ésimo elemento del diccionario, luego puede verificar si la palabra está en el diccionario más allá . Para hacer esto, considere el elemento del diccionario , donde denota el redondeo del número . Si , entonces debemos ir a la mitad derecha de la matriz, de lo contrario, a la izquierda. Al final, obtenemos el índice de la primera palabra, que es igual o lexicográficamente mayor que . $D$ $norte$ $O(1)$ ${\ estilo de visualización D (k)}$ $k$ $\omega$ $O(\log n)$ $D(\lpiso n/2\rpiso)$ $\lpiso ~\rpiso$ $D(\lpiso n/2\rpiso)<\omega$ $\omega$

int find ( vector < cadena > & D , cadena w ) { entero norte = re . tamaño (); intl = -1 , r = norte ; _ mientras ( r - l > 1 ) { int metro = ( l + r ) / 2 ; si ( re [ metro ] < w ) { l = metro ; } más { r = m ; } } devuelve r ; }

Tiempo polilogarítmico

Se dice que un algoritmo se ejecuta en tiempo polilogarítmico si para algunos . Por ejemplo, el problema del orden de la multiplicación de matrices se puede resolver en un tiempo así en una máquina RAM paralela [4] . $T(n)=O(\log ^{k}n)$ $k$

Tiempo sublineal

Se dice que un algoritmo se ejecuta en tiempo sublineal si . En particular, esto incluye algoritmos cuya complejidad temporal es como la anterior, así como, por ejemplo, la búsqueda de Grover con complejidad . ${\ estilo de visualización T (n) = o (n)}$ $O(n^{{1/2}})$

Por lo general, los algoritmos que, si bien son exactos, aún se ejecutan en tiempo sublineal, usan paralelismo de procesos (como lo hace el algoritmo de cálculo del determinante de matriz NC 1 ), cálculos no clásicos (como en la búsqueda de Grover) o tienen una conjetura garantizada en la estructura de entrada (como algoritmos de búsqueda binaria y muchos algoritmos de procesamiento de árboles). Sin embargo, los lenguajes formales , como el lenguaje de las palabras que tienen un bit 1 en la posición determinada por los primeros bits de la palabra, pueden ser decidibles en tiempo sublineal, aunque cualquier bit puede ser importante para determinar si una palabra pertenece a un idioma. . $\log n$

El término algoritmo de tiempo de ejecución sublineal generalmente se usa para algoritmos que, a diferencia de los ejemplos anteriores, se ejecutan en modelos de máquinas secuenciales convencionales y no requieren un conocimiento a priori de la estructura de entrada [5] . Sin embargo, se les permite usar métodos probabilísticos , y más aún, muchas veces deben ser aleatorizados para cualquier tarea no trivial.

Dado que dicho algoritmo debe dar una respuesta sin leer completamente los datos de entrada, depende mucho de los métodos de acceso permitidos en el flujo de entrada. Por lo general, para un flujo que es una cadena de bits , se supone que el algoritmo puede solicitar un valor para cualquier . ${\displaystyle b_{1},\puntos,b_{k))$ $O(1)$ $bi}$ $i$

Los algoritmos de tiempo sublineal suelen ser probabilísticos y dan solo una solución aproximada . Los algoritmos de tiempo de ejecución sublineales surgen naturalmente al explorar la verificación de propiedades .

Tiempo lineal

Se dice que un algoritmo se ejecuta en tiempo lineal , o en el tiempo si su complejidad lo es . Informalmente, esto significa que para un tamaño de entrada suficientemente grande, el tiempo de ejecución aumenta linealmente con el tamaño de la entrada. Por ejemplo, un procedimiento que suma todos los elementos de una lista lleva un tiempo proporcional a la longitud de la lista. Esta descripción no es del todo precisa, ya que el tiempo de ejecución puede diferir significativamente de la proporcionalidad exacta, especialmente para valores pequeños de . $En)$ $En)$ $norte$

El tiempo lineal se ve a menudo como un atributo deseable de un algoritmo [6] . Se ha investigado mucho para crear algoritmos con tiempos de ejecución (casi) lineales o mejores. Estos estudios incluyeron enfoques tanto de software como de hardware. En el caso de la ejecución de hardware, algunos algoritmos que, desde un punto de vista matemático, nunca pueden lograr un tiempo de ejecución lineal en los modelos informáticos estándar , pueden ejecutarse en tiempo lineal. Existen algunas tecnologías de hardware que utilizan el paralelismo para lograr este objetivo. Un ejemplo es la memoria asociativa . Este concepto de tiempo lineal se utiliza en problemas de coincidencia de patrones , como el algoritmo de Boyer-Moore y el algoritmo de Ukkonen .

Tiempo cuasi-lineal

Se dice que un algoritmo se ejecuta en un tiempo casi lineal si para alguna constante . Cuando hablan de tiempo lineal-logarítmico [7] . En términos de soft-O , dicho tiempo de ejecución se escribe como . Para algoritmos con tiempo de ejecución casi lineal, la estimación de any también es cierta . Por lo tanto, estos algoritmos son más rápidos que cualquier polinomio en , cuyo grado es mayor que . $T(n)=O(n\log ^{k}n)$ $k$ $k=1$ ${\tilde {O}}(n)$ $T(n)\in o(n^{1+\varepsilon})$ $\varepsilon >0$ $norte$ $una$

Los algoritmos que se ejecutan en tiempo casi lineal, además de los algoritmos logarítmicos lineales mencionados anteriormente, incluyen:

Clasificación de combinación en el lugar : ; $O(n\log ^{2}n)$
Clasificación rápida : la expectativa matemática del tiempo de ejecución de la versión probabilística del algoritmo se encuentra en cualquier entrada, para la versión determinista , esta estimación es correcta solo en promedio sobre todas las entradas; $O(n\log n)$
Heap sort , merge sort , introsort , binary tree sort , fluent sort , solitario sort y otros: peor de los casos; $O(n\log n)$
Transformada Rápida de Fourier : ; $O(n\log n)$
Algoritmos sobre matrices de Monge : . $O(n\log n)$

Tiempo logarítmico lineal

Logarítmico lineal es un caso especial de tiempo cuasi lineal con un exponente en un factor logarítmico. $k=1$

Una función logarítmica lineal es una función de la forma (es decir, el producto de un término lineal y logarítmico ). Se dice que el algoritmo se ejecuta en tiempo logarítmico lineal si [8] . Así, una función logarítmica lineal crece más rápido que una lineal, pero más lento que cualquier polinomio de grado mayor que . ${\ estilo de visualización n \ registro n}$ $T(n)=O(n\log n)$ $norte$ $una$

En muchos casos, el tiempo de ejecución es simplemente el resultado de realizar una operación de tiempo en el tiempo de ejecución . Por ejemplo, ordenar con un árbol binario crea un árbol binario insertando cada elemento de una matriz de tamaño uno por uno. Dado que la operación de inserción en un árbol de búsqueda binario equilibrado lleva tiempo , el tiempo total de ejecución del algoritmo será logarítmico lineal. ${\ estilo de visualización n \ registro n}$ $norte$ $O(\log n)$ $norte$ $O(\log n)$

Cualquier clasificación basada en comparaciones requiere al menos un número logarítmico lineal de comparaciones en el peor de los casos. Una de las justificaciones simples de este hecho desde el punto de vista de la teoría de la información es la siguiente: como resultado de la clasificación, obtenemos una permutación de longitud , que determina de manera única el orden de los elementos. Hay diferentes clasificaciones en total, si queremos codificar sin ambigüedades cada una de ellas con alguna secuencia de bits, necesitaremos en promedio no menos de bits de información por permutación. En este caso, el resultado de una comparación por pares de dos elementos de matriz es exactamente un bit de información: el primer elemento es menor que el segundo o no. Por lo tanto, si usamos solo comparaciones por pares para ordenar, no es posible ordenar una matriz en el mejor de los casos en el peor de los casos. Al mismo tiempo, dicha estimación para muchas ordenaciones recursivas, como la ordenación por combinación , a menudo surge de una ecuación recursiva . $norte$ $¡norte!$ ${\ estilo de visualización \ log n! \ sim n \ log n}$ $O(n\log n)$ ${\ estilo de visualización T (n) = T (n/2) + O (n)}$

Tiempo subcuadrado

Se dice que un algoritmo se ejecuta en tiempo subcuadrático si . $T(n)=o(n^{2})$

Por ejemplo, los algoritmos de clasificación simples basados en comparaciones (como la clasificación por inserción ) son cuadráticos. Al mismo tiempo, se pueden encontrar algoritmos más avanzados que tienen un tiempo de ejecución subcuadrático (por ejemplo, Shell sort ). Ninguna ordenación general funciona en tiempo lineal, pero la transición del tiempo cuadrático al subcuadrado es de gran importancia práctica.

Tiempo polinomial

Se dice que un algoritmo se ejecuta en tiempo polinomial si el tiempo de ejecución está acotado desde arriba por un polinomio en el tamaño de entrada del algoritmo, es decir, para alguna constante [1] [9] . Los problemas para los que existen algoritmos deterministas de tiempo polinomial constituyen la clase de complejidad P , que es fundamental para la teoría de la complejidad computacional . La tesis de Cobham establece que el tiempo polinomial es sinónimo de "fácil de procesar", "factible", "eficiente" o "rápido" [10] . $T(n)=O(n^{k})$ $k$

Algunos ejemplos de algoritmos polinómicos:

El algoritmo de clasificación rápida de enteros realiza operaciones máximas para algunas constantes . Así que funciona y es un algoritmo polinomial. $norte$ $An^{2}$ $A$ $O(n^{2})$
Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinomial.
La coincidencia máxima en gráficos se puede encontrar en tiempo polinomial.

Tiempo polinomial estricto y débil

En algunos contextos, especialmente en optimización , se hace una distinción entre algoritmos de tiempo polinomial estricto y tiempo polinomial débil . Estos dos conceptos solo se aplican a las entradas que consisten en números enteros.

El tiempo estrictamente polinomial se define en el modelo aritmético de cálculo. En este modelo, las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se toman como unidades de ejecución, independientemente de la longitud de los operandos. El algoritmo funciona en tiempo estrictamente polinomial si [11]

el número de operaciones en el modelo de cálculo aritmético está limitado a un polinomio en el número de enteros en el flujo de entrada, y
la memoria utilizada por el algoritmo está limitada por un polinomio en los tamaños de la entrada.

Cualquier algoritmo con estas dos propiedades puede reducirse a un algoritmo de tiempo polinomial reemplazando las operaciones aritméticas con los algoritmos correspondientes para realizar operaciones aritméticas en una máquina de Turing . Si no se cumple el segundo de los requisitos anteriores, esto dejará de ser cierto. Dado un número entero (que ocupa una memoria proporcional a n en una máquina de Turing), se puede calcular en n operaciones usando exponenciación repetida . Sin embargo, la memoria utilizada para representar es proporcional a y depende exponencialmente en lugar de polinomialmente de la memoria utilizada para la entrada. Por lo tanto, es imposible realizar estos cálculos en tiempo polinomial en una máquina de Turing, pero se puede realizar en un número polinomial de operaciones aritméticas. $2^{n}$ $2^{{2^{n}}}$ $2^{{2^{n}}}$ $2^{n}$

Por el contrario, hay algoritmos que funcionan en el número de pasos de la máquina de Turing, limitados por la longitud del polinomio de la entrada codificada en binario, pero no funcionan en el número de operaciones aritméticas, limitados por el polinomio en el número de números en el aporte. El algoritmo de Euclides para calcular el máximo común divisor de dos enteros es un ejemplo. Para dos números enteros y el tiempo de ejecución del algoritmo está limitado por los pasos de la máquina de Turing. Este número es un polinomio del tamaño de la representación binaria de números y , que se puede representar aproximadamente como . Al mismo tiempo, la cantidad de operaciones aritméticas no puede limitarse por la cantidad de números enteros en la entrada (que en este caso es una constante; solo hay dos números en la entrada). En vista de esta observación, el algoritmo no funciona en tiempo estrictamente polinomial. El tiempo de ejecución real del algoritmo depende de los valores y , y no solo del número de enteros en la entrada. $a$ $b$ $O((\log\a+\log\b)^{2})$ $a$ $b$ ${\ estilo de visualización \ registro \ a + \ registro \ b}$ $a$ $b$

Si un algoritmo se ejecuta en tiempo polinómico pero no estrictamente polinomial, se dice que se ejecuta en tiempo débilmente polinomial [12] . Un ejemplo bien conocido de un problema para el cual se conoce un algoritmo débilmente polinomial pero no se conoce un algoritmo estrictamente polinomial es la programación lineal . El tiempo débilmente polinómico no debe confundirse con el tiempo pseudopolinomial .

Clases de dificultad

El concepto de tiempo polinómico conduce a varias clases de complejidad en la teoría de la complejidad computacional. Algunas clases importantes definidas usando tiempo polinomial se enumeran a continuación.

P : Clase de complejidad de los problemas de solucionabilidad que se pueden resolver en una máquina de Turing determinista en tiempo polinomial.
NP : Clase de complejidad de los problemas de resolubilidad que se pueden resolver en una máquina de Turing no determinista en tiempo polinomial.
ZPP : Clase de complejidad de problemas de resolubilidad que pueden resolverse con error cero en una máquina de Turing probabilística en tiempo polinomial.
RP : Clase de complejidad de los problemas de resolubilidad que pueden resolverse con errores unilaterales en una máquina de Turing probabilística en tiempo polinomial.
BPP : Clase de complejidad de problemas de resolubilidad que pueden resolverse con errores bilaterales en una máquina de Turing probabilística en tiempo polinomial.
BQP : Clase de complejidad de los problemas de solucionabilidad que pueden resolverse con errores bilaterales en una máquina cuántica de Turing en tiempo polinomial.

P es la clase de complejidad de tiempo más pequeña en una máquina determinista que es estable términos de cambio de modelo de máquina. (Por ejemplo, pasar de una máquina de Turing de una sola cinta a una máquina de Turing de varias cintas podría resultar en una aceleración cuadrática, pero cualquier algoritmo que se ejecute en tiempo polinomial en un modelo se ejecutará en tiempo polinomial en otro).

Tiempo superpolinomio

Se dice que el algoritmo se ejecuta en tiempo superpolinomio , si T ( n ) no está acotado superiormente por un polinomio. Este tiempo es ω( n c ) para todas las constantes c , donde n es un argumento de entrada, normalmente el número de bits de entrada.

Por ejemplo, un algoritmo que toma 2n pasos requiere tiempo superpolinomial (más específicamente, tiempo exponencial) para una entrada de tamaño n .

Está claro que un algoritmo que usa recursos exponenciales es superpolinomio, pero algunos algoritmos son superpolinomios muy débiles. Por ejemplo, la prueba de primalidad de Adleman-Pomerance-Rumeli se ejecuta en un tiempo de n O (log log n ) en una entrada de n bits. Este crece más rápido que cualquier polinomio para n suficientemente grande , pero el tamaño de la entrada debe volverse muy grande para que no esté dominado por un polinomio de grado pequeño.

Un algoritmo que requiere un tiempo superpolinomial se encuentra fuera de la clase de complejidad P . La tesis de Cobham establece que estos algoritmos no son prácticos, y en muchos casos lo son. Dado que el problema de la igualdad de las clases P y NP no ha sido resuelto, actualmente no se conocen algoritmos para resolver problemas NP-completos en tiempo polinomial.

Tiempo cuasipolinomio

Los algoritmos de tiempo cuasipolinomial son algoritmos que se ejecutan más lento que el tiempo polinomial, pero no tan lento como los algoritmos de tiempo exponencial. El tiempo de ejecución en el peor de los casos para un algoritmo cuasi-polinomio es igual para algún c fijo . Un algoritmo clásico bien conocido para factorizar un número entero, el método general de tamiz de campos numéricos , que se ejecuta en aproximadamente el tiempo , no es cuasi-polinomio porque el tiempo de ejecución no se puede representar como para algún c fijo . Si la constante "c" en la definición del algoritmo de tiempo cuasi-polinomial es 1, obtenemos el algoritmo de tiempo polinomial, y si es menor que 1, obtenemos el algoritmo de tiempo sublineal. ${\displaystyle 2^{O((\log n)^{c)))))$ ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O((\log n)^{c)))))$

Los algoritmos de tiempo cuasi-polinomial generalmente surgen cuando se reduce un problema NP-difícil a otro problema. Por ejemplo, puede tomar un problema NP-difícil, digamos 3SAT , y reducirlo a otro problema B, pero el tamaño del problema se convierte en . En este caso, la reducción no prueba que el problema B sea NP-difícil, tal reducción solo muestra que no hay un algoritmo polinomial para B, a menos que exista un algoritmo cuasi-polinomio para 3SAT (y luego para todos los problemas NP ) . De manera similar, hay algunos problemas para los que conocemos algoritmos con tiempo cuasi-polinomial, pero para los cuales se desconocen algoritmos con tiempo polinomial. Estos problemas aparecen en los algoritmos de aproximación. Un ejemplo famoso es el problema de Steiner orientado , para el cual existe un algoritmo cuasi-polinomio aproximado con un coeficiente de aproximación (donde n es el número de vértices), pero la existencia de un algoritmo de tiempo polinomial es un problema abierto. ${\displaystyle 2^{O((\log n)^{c)))))$ $O(\log ^{3}n)$

La clase de complejidad QP consiste en todos los problemas que tienen algoritmos de tiempo cuasi polinomiales. Se puede definir en términos de DTIME de la siguiente manera [13] :

{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})

Relación con problemas NP-completos

En la teoría de la complejidad, el problema no resuelto de la igualdad de las clases P y NP pregunta si todos los problemas de la clase NP tienen algoritmos de solución en tiempo polinomial. Todos los algoritmos conocidos para problemas NP-completos , como 3SAT, tienen tiempo exponencial. Además, existe la conjetura de que para muchos problemas naturales NP-completos no existen algoritmos con tiempo de ejecución subexponencial. Aquí "tiempo subexponencial" se toma en el sentido de la segunda definición dada a continuación. (Por otro lado, muchos problemas de teoría de grafos naturalmente representados por matrices de adyacencia se pueden resolver en tiempo subexponencial simplemente porque el tamaño de la entrada es el cuadrado del número de vértices). Esta conjetura (para el problema k-SAT) se conoce como la conjetura del tiempo exponencial [14] . Dado que asume que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales, algunos resultados de no aproximabilidad en el campo de los algoritmos de aproximación asumen que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales. Por ejemplo, vea los resultados conocidos sobre la no aproximabilidad del problema de cobertura de conjuntos .

Tiempo subexponencial

El término tiempo subexponencial [ se usa para expresar que el tiempo de ejecución de algún algoritmo puede crecer más rápido que cualquier polinomio, pero sigue siendo sustancialmente menor que el exponencial. En este sentido, los problemas que tienen algoritmos de tiempo sub-exponencial son más maleables que los algoritmos con solo tiempo exponencial. La definición exacta de "subexponencial" aún no se acepta de forma general [15] , y a continuación damos dos de las definiciones más comunes.

Primera definición

Se dice que un problema se resuelve en tiempo subexponencial si se resuelve mediante un algoritmo cuyo logaritmo del tiempo de ejecución crece menos que cualquier polinomio dado. Más precisamente, un problema tiene un tiempo subexponencial si para cualquier ε > 0 existe un algoritmo que resuelve el problema en un tiempo O(2 n ε ). El conjunto de todos estos problemas constituye la clase de complejidad SUBEXP , que se puede expresar en términos de DTIME como [3] [16] [17] [18] .

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

Tenga en cuenta que aquí ε no es parte de los datos de entrada, y cada ε puede tener su propio algoritmo para resolver el problema.

Segunda definición

Algunos autores definen el tiempo subexponencial como el tiempo de ejecución 2 o( n ) [14] [19] [20] . Esta definición permite un tiempo de ejecución más largo que la primera definición. Un ejemplo de un algoritmo de tiempo subexponencial de este tipo es el conocido algoritmo clásico para factorizar enteros, el método general de criba de campos numéricos , que se ejecuta aproximadamente en el tiempo , donde la longitud de entrada es n . Otro ejemplo es el conocido algoritmo para el problema de isomorfismo de grafos , cuyo tiempo de ejecución es . ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O({\sqrt {n\log n))))$

Tenga en cuenta que existe una diferencia si el algoritmo es subexponencial en el número de vértices o en el número de aristas. En la complejidad parametrizada , esta diferencia está explícitamente presente al especificar el par , el problema de solución y el parámetro k . SUBEPT es la clase de todos los problemas parametrizados que se ejecutan en tiempo subexponencial en k y en tiempo polinomial en n [21] : ${\ estilo de visualización (L, k)}$

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

Más precisamente, SUBEPT es la clase de todos los problemas parametrizados para los cuales existe una función computable c y un algoritmo que resuelve L en el tiempo . ${\ estilo de visualización (L, k)}$ $f:\mathbb {N} \to \mathbb {N}$ ${\ estilo de visualización f \ en o (k)}$ $2^{f(k)}\cdot {\text{poli}}(n)$

La conjetura del tiempo exponencial

La Conjetura del Tiempo Exponencial (' ETH ) establece que 3SAT , el problema de satisfacibilidad para fórmulas booleanas en forma normal conjuntiva con un máximo de tres literales por oración y n variables, no se puede resolver en el tiempo 2o ( n ) . Más precisamente, la conjetura dice que existe una constante c >0 tal que 3SAT no puede resolverse en 2 cn en ninguna máquina de Turing determinista. Si m denota el número de oraciones, ETH es equivalente a la hipótesis de que k -SAT no se puede resolver en el tiempo 2 o ( m ) para cualquier número entero k ≥ 3 [22] . De la hipótesis del tiempo exponencial se sigue que P ≠ NP .

Tiempo exponencial

Se dice que un algoritmo se ejecuta en tiempo exponencial si T ( n ) está acotado arriba por 2 poli( n ) , donde poli( n ) es algún polinomio en n . Más formalmente, el algoritmo se ejecuta en tiempo exponencial si T ( n ) está acotado O(2 n k ) con alguna constante k . Las tareas que se ejecutan en tiempo exponencial en máquinas de Turing deterministas forman la clase de complejidad EXP .

{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)

A veces, el término tiempo exponencial se usa para algoritmos para los cuales T ( n ) = 2 O ( n ) , donde el exponente es como máximo una función lineal de n . Esto da como resultado la clase de complejidad E .

{\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)

Doble tiempo exponencial

Se dice que un algoritmo se ejecuta en tiempo doblemente exponencial si T ( n ) está acotado arriba por 2 2 poly( n ) , donde poly( n ) es algún polinomio en n . Dichos algoritmos pertenecen a la clase de complejidad 2-EXPTIME .

{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{2^{n^{c}}}})

Los algoritmos doblemente exponenciales bien conocidos incluyen:

Procedimiento de cálculo para la aritmética de Presburger
Cálculo de la base de Gröbner (peor caso [23] )
La eliminación de cuantificadores en campos cerrados reales requiere al menos el doble del tiempo de ejecución exponencial [24] y se puede hacer en este tiempo [25] .

Véase también

notación L
Dificultad de memoria

Notas

↑ 12 Michael Sipser . Introducción a la Teoría de la Computación. - Course Technology Inc, 2006. - ISBN 0-619-21764-2 .
↑ Kurt Mehlhorn, Stefan Naher. Diccionarios ordenados acotados en tiempo O(log log N) y espacio O(n) // Cartas de procesamiento de información. - 1990. - T. 35 , núm. 4 . - S. 183 . -doi : 10.1016 / 0020-0190(90)90022-P .
↑ 1 2 László Babai, Lance Fortnow, N. Nisan, Avi Wigderson. BPP tiene simulaciones de tiempo subexponenciales a menos que EXPTIME tenga pruebas publicables // Complejidad computacional. - Berlín, Nueva York: Springer-Verlag , 1993. - Vol. 3 , núm. 4 . - S. 307-318 . -doi : 10.1007/ BF01275486 .
↑ JE Rawlins, Gregory E. Shannon. Ordenación eficiente de cadenas de matrices en tiempo de polílog // SIAM Journal on Computing. - Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas , 1998. - V. 27 , no. 2 . - S. 466-490 . — ISSN 1095-7111 . -doi : 10.1137/ S0097539794270698 .
↑ Ravi Kumar, Ronitt Rubinfeld. Algoritmos de tiempo sublineal // Noticias SIGACT. - 2003. - T. 34 , núm. 4 . - S. 57-67 . -doi : 10.1145/ 954092.954103 .
↑ DR KN PRASANNA KUMAR, PROF BS KIRANAGI Y PROF CS BAGEWADI. UNA TEORÍA GENERAL DEL SISTEMA 'INFORMACIÓN CUÁNTICA - ENLACE CUÁNTICO, DECAIMIENTO DE PARTÍCULAS SUBATÓMICAS - ESTADOS DE GIRO ASIMÉTRICO, VARIABLES NO OCULTAS LOCALMENTE - UN MODELO CONCATENADO // Revista Internacional de Publicaciones Científicas y de Investigación. - Julio 2012. - Vol. 2 , núm. 7 . — ISSN 22503153 .
↑ Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. Sobre la teoría de la complejidad del tiempo cuasilineal // Ciencias de la computación teórica. — vol. 148 . - Pág. 325-349 .
↑ Sedgewick, R. y Wayne K (2011). Algorithms, 4th Ed Archivado el 15 de julio de 2014 en Wayback Machine . pags. 186. Educación de Pearson, Inc.
↑ Christos H. Papadimitriou. Complejidad computacional. - Lectura, Mass.: Addison-Wesley, 1994. - ISBN 0-201-53082-1 .
↑ Alan Cobham. proc. Lógica, Metodología y Filosofía de la Ciencia II. - Holanda Septentrional, 1965. - C. La dificultad computacional intrínseca de las funciones.
↑ Martin Grötschel, László Lovász , Alexander Schrijver . Algoritmos Geométricos y Optimización Combinatoria. - Springer, 1988. - C. Complejidad, Oráculos y Computación Numérica. — ISBN 0-387-13624-X .
↑ Alexander Schrijver. Optimización Combinatoria: Poliedros y Eficiencia. - Springer, 2003. - V. 1. - C. Preliminares sobre algoritmos y Complejidad. — ISBN 3-540-44389-4 .
↑ Complexity Zoo Archivado el 26 de julio de 2010 en Wayback Machine Class QP: Quasipolynomial-Time Archivado el 22 de diciembre de 2015 en Wayback Machine .
↑ 1 2 R. Impagliazzo, R. Paturi. Sobre la complejidad de k-SAT // Journal of Computer and System Sciences. - Elsevier , 2001. - T. 62 , núm. 2 . - S. 367-375 . — ISSN 1090-2724 . doi : 10.1006 / jcss.2000.1727 .
↑ Aaronson, Scott. Un dilema no del todo exponencial. — 5 de abril de 2009.
↑ Complexity Zoo Archivado el 26 de julio de 2010 en Wayback Machine Class SUBEXP: Deterministic Subexponential-Time Archivado el 27 de agosto de 2016 en Wayback Machine .
↑ P. Moser. Categorías de Bare sobre clases de complejidad pequeña // Apuntes de conferencias en informática . - Berlín, Nueva York: Springer-Verlag, 2003. - S. 333-342 . — ISSN 0302-9743 .
↑ PB Miltersen. DERANDOMIZANDO LAS CLASES DE COMPLEJIDAD // Manual de computación aleatoria. - Publicación académica Kluwer, 2001. - P. 843 .
↑ Greg Kuperberg. Un algoritmo cuántico de tiempo subexponencial para el problema del subgrupo oculto diedro // SIAM Journal on Computing. - Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas , 2005. - V. 35 , no. 1 . - S. 188 . — ISSN 1095-7111 . -doi : 10.1137/ s0097539703436345 .
↑ Oded Regev. Un algoritmo de tiempo subexponencial para el problema del subgrupo oculto diedro con espacio polinomial . — 2004.
↑ Jörg Flum, Martin Grohe. Teoría de la Complejidad Parametrizada. - Springer, 2006. - Pág. 417. - ISBN 978-3-540-29952-3 .
↑ R. Impagliazzo, R. Paturi, F. Zane. ¿Qué problemas tienen una complejidad fuertemente exponencial? // Revista de Ciencias de la Computación y Sistemas . - 2001. - T. 63 , núm. 4 . - S. 512-530 . -doi : 10.1006/ jcss.2001.1774 .
↑ Mayr, E. y Mayer, A. La complejidad del problema verbal para semigrupos conmutativos e ideales polinómicos // Adv. en Matemáticas.. - 1982. - Edición. 46 . - S. 305-329 .
↑ JH Davenport, J. Heintz. La eliminación del cuantificador real es doblemente exponencial // J. Symbolic Comp. - 1988. - vol. 5 . - S. 29-35 . .
↑ GE Collins. proc. 2do. Conferencia GI Teoría de autómatas y lenguajes formales. — Springer. - T. 33. - S. 134-183. — (Apuntes de clase en informática).