complejidad temporal

{\displaystyle N} — Gráficas de funciones comúnmente utilizadas en el análisis de algoritmos , que muestran el número de operaciones. $N$ como resultado del tamaño de entrada $n$ para cada función

En informática teórica , la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo de computación que requiere ejecutar un algoritmo . La complejidad temporal se suele estimar contando el número de operaciones elementales que realiza el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, se considera que el tiempo empleado y el número de operaciones elementales realizadas por el algoritmo están relacionados por un factor constante .

Dado que el tiempo de ejecución de un algoritmo puede variar entre diferentes entradas del mismo tamaño, comúnmente se considera la complejidad temporal en el peor de los casos , que es el tiempo máximo requerido para entradas de un tamaño dado. Menos común, y generalmente especificada explícitamente, es la complejidad en el caso promedio , que es el promedio del tiempo empleado en entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de posibles entradas de un tamaño dado). En ambos casos, la complejidad temporal generalmente se expresa como una función del tamaño de la entrada. ^{[ 1 ]}^{: 226} Dado que esta función generalmente es difícil de calcular con exactitud, y el tiempo de ejecución para entradas pequeñas generalmente no es relevante, comúnmente se centra la atención en el comportamiento de la complejidad cuando el tamaño de la entrada aumenta, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente utilizando la notación O grande , típicamente $O(n)$ , $O(n\log n)$ , $O(n^{\alpha })$ , $O(2^{n})$ , etc., donde $n$ es el tamaño en unidades de bits necesario para representar la entrada.

Las complejidades algorítmicas se clasifican según el tipo de función que aparece en la notación O grande. Por ejemplo, un algoritmo con complejidad temporal $O(n)$ es un algoritmo de tiempo lineal y un algoritmo con complejidad temporal $O(n^{\alpha })$ por alguna constante $\alpha >0$ es un algoritmo de tiempo polinomial .

Tabla de complejidades temporales comunes

La siguiente tabla resume algunas clases de complejidades temporales que se encuentran comúnmente. En la tabla, ${\text{poly}}(x)=x^{O(1)}$ , es decir, polinomio en $x$ .

Un algoritmo se denomina de tiempo constante (a menudo representado como $O(1)$ tiempo) cuando su función de complejidad $T(n)$ Está limitado por un valor que no cambia con el tamaño de la entrada. Esto implica que el tiempo de ejecución permanece constante independientemente de la cantidad de datos procesados. Por ejemplo, acceder a un elemento específico en un array es una operación de tiempo constante, ya que solo requiere una operación para localizar dicho elemento.

Por el contrario, determinar el valor mínimo en una matriz no ordenada no es de tiempo constante; requiere examinar cada elemento , lo que resulta en una complejidad de tiempo lineal, o $O(n)$ Sin embargo, si se conoce y se fija el número de elementos, ciertas tareas aún pueden considerarse de tiempo constante.

Es importante destacar que el término "tiempo constante" no significa que el tiempo de ejecución deba ser completamente independiente del tamaño del problema; más bien, debe tener un límite superior consistente independientemente del tamaño de la entrada. Por ejemplo, una tarea que implica intercambiar los valores de $a$ y $b$ para asegurar $a\leq b$ Se clasifica como de tiempo constante, aunque el tiempo de ejecución puede variar dependiendo de si la condición ya se ha cumplido. La clave es que existe una constante. $t$ de tal manera que el tiempo empleado nunca exceda $t$ , independientemente de los valores de entrada.

Los algoritmos de tiempo constante son especialmente importantes en contextos como la criptografía, donde los ataques de temporización pueden explotar las variaciones en el tiempo de ejecución. Al diseñar algoritmos que se ejecutan en tiempo constante, los desarrolladores pueden mejorar la seguridad y garantizar la previsibilidad del rendimiento, lo que lo convierte en una consideración fundamental en la ingeniería de software.

Tiempo logarítmico

Se dice que un algoritmo tarda tiempo logarítmico cuando $T(n)=O(\log n)$ . Desde $\log _{a}n$ y $\log _{b}n$ están relacionados por un multiplicador constante , y dicho multiplicador es irrelevante para la clasificación de la gran O, el uso estándar para algoritmos de tiempo logarítmico es $O(\log n)$ independientemente de la base del logaritmo que aparece en la expresión de $T$ .

Los algoritmos que requieren tiempo logarítmico se encuentran comúnmente en operaciones con árboles binarios o al usar la búsqueda binaria .

Un $O(\log n)$ El algoritmo se considera altamente eficiente, ya que la relación entre el número de operaciones y el tamaño de la entrada disminuye y tiende a cero cuando $n$ aumenta. Un algoritmo que debe acceder a todos los elementos de su entrada no puede tomar tiempo logarítmico, ya que el tiempo que se tarda en leer una entrada de tamaño $n$ es del orden de $n$ .

Un ejemplo de tiempo logarítmico lo proporciona la búsqueda en un diccionario. Consideremos un diccionario. $D$ que contiene $n$ entradas, ordenadas alfabéticamente . Suponemos que, para $1\leq k\leq n$ , uno puede acceder al $k$ -ésima entrada del diccionario en un tiempo constante. Sea $D(k)$ denota esto $k$ -ésima entrada. Bajo estas hipótesis, la prueba para ver si una palabra $w$ está en el diccionario puede hacerse en tiempo logarítmico: considere $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ , dónde $\lfloor \;\rfloor$ denota la función piso . Si $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ —es decir, la palabra $w$ está exactamente en el medio del diccionario, entonces hemos terminado. De lo contrario, si $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ --es decir, si la palabra $w$ Si la palabra aparece antes en orden alfabético que la palabra central del diccionario, continuamos la búsqueda de la misma manera en la mitad izquierda (es decir, la primera) del diccionario, y luego repetimos el proceso hasta encontrar la palabra correcta. De lo contrario, si aparece después de la palabra central, continuamos de forma similar con la mitad derecha del diccionario. Este algoritmo es similar al método que se suele usar para encontrar una entrada en un diccionario impreso. Como resultado, el espacio de búsqueda dentro del diccionario se reduce a medida que el algoritmo se acerca a la palabra objetivo.

Tiempo polilogarítmico

Se dice que un algoritmo se ejecuta en tiempo polilogarítmico si su tiempo $T(n)$ es $O{\bigl (}(\log n)^{k}{\bigr )}$ por alguna constante $k$ Otra forma de escribir esto es $O(\log ^{k}n)$ .

Por ejemplo, el ordenamiento de cadenas de matrices se puede resolver en tiempo polilogarítmico en una máquina de acceso aleatorio paralela , ^{[ 7 ]} y se puede determinar que un grafo es planar de una manera totalmente dinámica en $O(\log ^{3}n)$ tiempo por operación de inserción/eliminación. ^{[ 8 ]}

Tiempo sublineal

Se dice que un algoritmo se ejecuta en tiempo sublineal (a menudo escrito tiempo sublineal ) si $T(n)=o(n)$ En particular, esto incluye algoritmos con las complejidades temporales definidas anteriormente.

El término específico algoritmo de tiempo sublineal se refiere comúnmente a algoritmos aleatorios que muestrean una pequeña fracción de sus entradas y las procesan de manera eficiente para inferir aproximadamente propiedades de toda la instancia. ^{[ 9 ]} Este tipo de algoritmo de tiempo sublineal está estrechamente relacionado con las pruebas de propiedades y la estadística .

Otros entornos en los que los algoritmos pueden ejecutarse en tiempo sublineal incluyen:

Algoritmos paralelos que tienen un trabajo total lineal o mayor (lo que les permite leer toda la entrada), pero una profundidad sublineal .
Algoritmos que tienen supuestos garantizados sobre la estructura de entrada. Un ejemplo importante son las operaciones sobre estructuras de datos , por ejemplo, la búsqueda binaria en un array ordenado.
Algoritmos que buscan estructura local en la entrada, por ejemplo encontrar un mínimo local en una matriz 1-D (se puede resolver en $O(\log(n))$ tiempo utilizando una variante de búsqueda binaria). Una noción estrechamente relacionada es la de los algoritmos de computación local (LCA), donde el algoritmo recibe una entrada grande y consulta información local sobre alguna salida grande válida. ^{[ 10 ]}

Tiempo lineal

Se dice que un algoritmo toma tiempo lineal , o $O(n)$ tiempo, si su complejidad temporal es $O(n)$ De manera informal, esto significa que el tiempo de ejecución aumenta como máximo linealmente con el tamaño de la entrada. Más precisamente, esto significa que hay una constante $c$ de tal manera que el tiempo de ejecución sea como máximo $cn$ para cada entrada de tamaño $n$ Por ejemplo, un procedimiento que suma todos los elementos de una lista requiere un tiempo proporcional a la longitud de la lista, si el tiempo de suma es constante o, al menos, está limitado por una constante.

El tiempo lineal es la mejor complejidad temporal posible en situaciones donde el algoritmo debe leer secuencialmente toda su entrada. Por lo tanto, se ha invertido mucho en investigación para descubrir algoritmos que presenten un tiempo lineal o, al menos, casi lineal. Esta investigación incluye métodos tanto de software como de hardware. Existen varias tecnologías de hardware que aprovechan el paralelismo para lograrlo. Un ejemplo es la memoria direccionable por contenido . Este concepto de tiempo lineal se utiliza en algoritmos de búsqueda de cadenas como el algoritmo de búsqueda de cadenas de Boyer-Moore y el algoritmo de Ukkonen .

Tiempo cuasilineal

Se dice que un algoritmo se ejecuta en tiempo cuasilineal (también denominado tiempo logarítmico lineal ) si $T(n)=O(n\log ^{k}n)$ para alguna constante positiva $k$ ; ^{[ 11 ]} el tiempo linealítmico es el caso $k=1$ . ^{[ 12 ]} Utilizando la notación O suave, estos algoritmos son ${\tilde {O}}(n)$ Los algoritmos de tiempo cuasilineal también lo son. $O(n^{1+\varepsilon })$ para cada constante $\varepsilon >0$ y por lo tanto se ejecutan más rápido que cualquier algoritmo de tiempo polinomial cuyo límite de tiempo incluye un término $n^{c}$ para cualquier $c>1$ .

Entre los algoritmos que se ejecutan en tiempo cuasilineal se incluyen:

Ordenación por fusión in situ , $O(n\log ^{2}n)$
Ordenación rápida , $O(n\log n)$ , en su versión aleatoria, tiene un tiempo de ejecución que es $O(n\log n)$ en expectativa sobre la entrada del peor caso. Su versión no aleatoria tiene una $O(n\log n)$ El tiempo de ejecución solo se tiene en cuenta al considerar la complejidad promedio del caso.
Ordenación por montículos , $O(n\log n)$ , ordenación por fusión , ordenación introsort , ordenación por árbol binario, ordenación suave , ordenación por paciencia , etc. en el peor de los casos
transformadas rápidas de Fourier , $O(n\log n)$
Cálculo de matriz de Monge , $O(n\log n)$
Algoritmo de Schönhage-Strassen para la multiplicación , $O(n\log n\log \log n)$

En muchos casos, el $O(n\log n)$ El tiempo de ejecución es simplemente el resultado de realizar una $\Theta (\log n)$ operación $n$ veces (para la notación, véase la notación Big O § Familia de notaciones de Bachmann-Landau ). Por ejemplo, la ordenación de árboles binarios crea un árbol binario insertando cada elemento del $n$ matriz de tamaño uno por uno. Dado que la operación de inserción en un árbol de búsqueda binaria autoequilibrado lleva $O(\log n)$ tiempo, todo el algoritmo tarda $O(n\log n)$ tiempo.

Las clasificaciones por comparación requieren al menos $\Omega (n\log n)$ comparaciones en el peor de los casos porque $\log(n!)=\Theta (n\log n)$ , por la aproximación de Stirling . También surgen frecuentemente de la relación de recurrencia. $T(n)=2T\left({\frac {n}{2}}\right)+O(n)$ .

Tiempo subcuadrático

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

Por ejemplo, los algoritmos de ordenación simples basados en comparaciones son cuadráticos (como el ordenamiento por inserción ), pero existen algoritmos más avanzados que son subcuadráticos (como el ordenamiento por capas ). Ningún algoritmo de ordenación de propósito general se ejecuta en tiempo lineal, pero el cambio de cuadrático a subcuadrático tiene una gran importancia práctica.

Tiempo polinomial

Se dice que un algoritmo es de tiempo polinomial si su tiempo de ejecución está acotado superiormente por una expresión polinomial en el tamaño de la entrada para el algoritmo, es decir, $1=T(n)=O(n^{k})$ para alguna constante positiva $k$ . ^{[ 1 ]}^{[ 13 ]} Los problemas para los que existe un algoritmo determinista de tiempo polinomial pertenecen a la clase de complejidad P , que es fundamental en el campo de la teoría de la complejidad computacional . La tesis de Cobham afirma que el tiempo polinomial es sinónimo de "tratable", "factible", "eficiente" o "rápido". ^{[ 14 ]}

Algunos ejemplos de algoritmos de tiempo polinomial:

El algoritmo de ordenación por selección en $n$ Los números enteros realizan $An^{2}$ operaciones para alguna constante $A$ Por lo tanto, corre a tiempo. $O(n^{2})$ y es un algoritmo de tiempo polinomial.
Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinomial.
Los emparejamientos máximos en grafos se pueden encontrar en tiempo polinomial. En algunos contextos, especialmente en optimización , se distingue entre algoritmos de tiempo polinomial fuerte y débil .

Estos dos conceptos solo son relevantes si las entradas de los algoritmos consisten en números enteros.

Clases de complejidad

El concepto de tiempo polinomial conduce a varias clases de complejidad en la teoría de la complejidad computacional. Algunas clases importantes definidas utilizando el tiempo polinomial son las siguientes.

P : La clase de complejidad de los problemas de decisión que pueden resolverse en una máquina de Turing determinista en tiempo polinomial.
NP : La clase de complejidad de problemas de decisión que pueden resolverse en una máquina de Turing no determinista en tiempo polinomial.
ZPP : La clase de complejidad de problemas de decisión que pueden resolverse con error cero en una máquina de Turing probabilística en tiempo polinomial.
RP : La clase de complejidad de problemas de decisión que pueden resolverse con error unilateral en una máquina de Turing probabilística en tiempo polinomial.
BPP : La clase de complejidad de problemas de decisión que pueden resolverse con error bilateral en una máquina de Turing probabilística en tiempo polinomial.
BQP : La clase de complejidad de problemas de decisión que pueden resolverse con error bilateral en una máquina de Turing cuántica en tiempo polinomial.

P es la clase de complejidad temporal más pequeña en una máquina determinista que es robusta en términos de cambios en el modelo de la máquina. (Por ejemplo, un cambio de una máquina de Turing de una sola cinta a una de múltiples cintas puede generar una aceleración cuadrática, pero cualquier algoritmo que se ejecute en tiempo polinomial bajo un modelo también lo hará en el otro). Cualquier máquina abstracta dada tendrá una clase de complejidad que corresponde a los problemas que se pueden resolver en tiempo polinomial en esa máquina.

Tiempo superpolinomial

Se define un algoritmo para que tome tiempo superpolinomial si $T(n)$ no está acotada superiormente por ningún polinomio; es decir, si $T(n)\not \in O(n^{c})$ para cada entero positivo $c$ .

Por ejemplo, un algoritmo que se ejecuta durante $2^{n}$ pasos en una entrada de tamaño $n$ requiere un tiempo superpolinomial (más específicamente, un tiempo exponencial).

Un algoritmo que utiliza recursos exponenciales es claramente superpolinomial, pero algunos algoritmos son solo muy débilmente superpolinomiales. Por ejemplo, la prueba de primalidad de Adleman-Pomerance-Rumely se ejecuta para $n^{O(\log \log n)}$ tiempo en $n$ entradas de bits; esto crece más rápido que cualquier polinomio para valores suficientemente grandes $n$ pero el tamaño de entrada debe volverse impracticablemente grande antes de que no pueda ser dominado por un polinomio de grado pequeño.

Un algoritmo que requiere tiempo superpolinomial queda fuera de la clase de complejidad P. La tesis de Cobham postula que estos algoritmos son poco prácticos, y en muchos casos lo son. Dado que el problema P versus NP no está resuelto, se desconoce si los problemas NP-completos requieren tiempo superpolinomial.

Tiempo cuasipolinomial

Los algoritmos de tiempo cuasipolinomial son algoritmos cuyo tiempo de ejecución presenta un crecimiento cuasipolinomial , un tipo de comportamiento que puede ser más lento que el tiempo polinomial, pero significativamente más rápido que el tiempo exponencial . El tiempo de ejecución en el peor de los casos de un algoritmo de tiempo cuasipolinomial es $2^{O(\log ^{c}n)}$ para algún fijo $c>0$ . Cuando $c=1$ esto da tiempo polinomial, y para $c<1$ Da un tiempo sublineal.

Hay algunos problemas para los que conocemos algoritmos de tiempo cuasipolinomial, pero no se conoce ningún algoritmo de tiempo polinomial. Estos problemas surgen en algoritmos de aproximación; un ejemplo famoso es el problema del árbol de Steiner dirigido , para el cual existe un algoritmo de aproximación de tiempo cuasipolinomial que alcanza un factor de aproximación de $O(\log ^{3}n)$ ( $n$ siendo el número de vértices), pero demostrar la existencia de un algoritmo de tiempo polinomial de este tipo es un problema abierto.

Otros problemas computacionales con soluciones de tiempo cuasipolinomial pero sin solución conocida de tiempo polinomial incluyen el problema de la camarilla plantada , cuyo objetivo es encontrar una camarilla grande en la unión de una camarilla y un grafo aleatorio . Aunque es resoluble en tiempo cuasipolinomial, se ha conjeturado que el problema de la camarilla plantada no tiene solución de tiempo polinomial; esta conjetura se ha utilizado como una suposición de dificultad computacional para demostrar la dificultad de varios otros problemas en teoría de juegos computacional , pruebas de propiedades y aprendizaje automático . ^{[ 15 ]}

La clase de complejidad QP consta de todos los problemas que tienen algoritmos de tiempo cuasi-polinomial. Se puede definir en términos de DTIME de la siguiente manera. ^{[ 16 ]}

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

Relación con problemas NP-completos

En la teoría de la complejidad, el problema sin resolver de P versus NP plantea si todos los problemas en NP tienen algoritmos de tiempo polinomial. Todos los algoritmos más conocidos para problemas NP-completos, como 3SAT, etc., requieren tiempo exponencial. De hecho, se conjetura para muchos problemas NP-completos naturales que no tienen algoritmos de tiempo subexponencial. Aquí, "tiempo subexponencial" se refiere a la segunda definición que se presenta a continuación. (Por otro lado, muchos problemas de grafos representados de forma natural mediante 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 hipótesis del tiempo exponencial . ^{[ 17 ]} Dado que se conjetura que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomial, algunos resultados de inaproximabilidad en el campo de los algoritmos de aproximación asumen que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomial. Por ejemplo, véanse los resultados de inaproximabilidad conocidos para el problema de cobertura de conjuntos .

Tiempo subexponencial

El término tiempo subexponencial se utiliza para indicar que el tiempo de ejecución de un algoritmo puede crecer más rápido que cualquier polinomio, pero sigue siendo significativamente menor que el de un algoritmo exponencial. En este sentido, los problemas que admiten algoritmos de tiempo subexponencial son algo más manejables que aquellos que solo admiten algoritmos exponenciales. No existe un consenso general sobre la definición precisa de "subexponencial" ^{[ 18 ]} , sin embargo, las dos más utilizadas se presentan a continuación.

Primera definición

Se dice que un problema es resoluble en tiempo subexponencial si puede resolverse en tiempos de ejecución cuyos logaritmos crecen más pequeños que cualquier polinomio dado. Más precisamente, un problema está en tiempo subexponencial si para cada $\epsilon >0$ Existe un algoritmo que resuelve el problema en tiempo $O(2^{n^{\epsilon }})$ . El conjunto de todos esos problemas es la clase de complejidad SUBEXP que se puede definir en términos de DTIME de la siguiente manera. ^{[ 6 ]}^{[ 19 ]}^{[ 20 ]}^{[ 21 ]}

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

Esta noción de subexponencial no es uniforme en términos de $\epsilon$ en el sentido de que $\epsilon$ no forma parte de la entrada y cada ε puede tener su propio algoritmo para el problema.

Segunda definición

Algunos autores definen el tiempo subexponencial como tiempos de ejecución en $2^{o(n)}$ . ^{[ 17 ]}^{[ 22 ]}^{[ 23 ]} Esta definición permite tiempos de ejecución mayores que la primera definición de tiempo subexponencial. Un ejemplo de un algoritmo de tiempo subexponencial es el algoritmo clásico más conocido para la factorización de enteros, la criba de cuerpos numéricos general , que se ejecuta en un tiempo de aproximadamente $2^{{O}(n^{1/3}(\log n)^{2/3})}$ , donde la longitud de la entrada es $n$ Otro ejemplo fue el problema del isomorfismo de grafos , que el mejor algoritmo conocido desde 1982 hasta 2016 resolvió en $2^{O\left({\sqrt {n\log n}}\right)}$ Sin embargo, en STOC 2016 se presentó un algoritmo de tiempo cuasipolinomial. ^{[ 24 ]}

Es importante si se permite que el algoritmo sea subexponencial en el tamaño de la instancia, el número de vértices o el número de aristas. En la complejidad parametrizada , esta diferencia se hace explícita al considerar pares. $(L,k)$ de problemas de decisión y parámetros $k$ . SUBEPT es la clase de todos los problemas parametrizados que se ejecutan en tiempo subexponencial en $k$ y polinomial en el tamaño de entrada $n$ : ^{[ 25 ]}

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

Más precisamente, SUBEPT es la clase de todos los problemas parametrizados. $(L,k)$ para la cual existe una función computable $f:\mathbb {N} \to \mathbb {N}$ con $f\in o(k)$ y un algoritmo que decide $L$ a tiempo $2^{f(k)}\cdot {\text{poly}}(n)$ .

Hipótesis del tiempo exponencial

La hipótesis del tiempo exponencial ( ETH ) es que 3SAT , el problema de satisfacibilidad de fórmulas booleanas en forma normal conjuntiva con como máximo tres literales por cláusula y con $n$ variables, no se puede resolver a tiempo $2^{o(n)}$ Más precisamente, la hipótesis es que existe alguna constante absoluta. $c>0$ de tal manera que 3SAT no se puede decidir a tiempo $2^{cn}$ por cualquier máquina de Turing determinista. Con $m$ que denota el número de cláusulas, ETH es equivalente a la hipótesis de que $k$ -SAT no se puede resolver a tiempo $2^{o(m)}$ para cualquier número entero $k\geq 3$ . ^{[ 26 ]} La hipótesis del tiempo exponencial implica P ≠ NP .

Tiempo exponencial

Se dice que un algoritmo es de tiempo exponencial si $T(n)$ está limitado superiormente por $2^{{\text{poly}}(n)}$ , dónde ${\text{poly}}(n)$ es algún polinomio en $n$ . Más formalmente, un algoritmo es de tiempo exponencial si $T(n)$ está delimitado por $O(2^{n^{k}})$ por alguna constante $k$ . Los problemas que admiten algoritmos de tiempo exponencial en una máquina de Turing determinista forman la clase de complejidad conocida como EXP .

{\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)

A veces, el tiempo exponencial se utiliza para referirse a algoritmos que tienen $T(n)=2^{O(n)}$ donde el exponente es como máximo una función lineal de $n$ Esto da lugar a la clase de complejidad E.

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

Tiempo factorial

Se dice que un algoritmo es de tiempo factorial si $T(n)$ está acotado superiormente por la función factorial $n!$ El tiempo factorial es un subconjunto del tiempo exponencial (EXP) porque $n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)$ a pesar de $\epsilon >0$ Sin embargo, no es un subconjunto de E.

Un ejemplo de un algoritmo que se ejecuta en tiempo factorial es bogosort , un algoritmo de ordenación notoriamente ineficiente basado en prueba y error . Bogosort ordena una lista de $n$ elementos reorganizando repetidamente la lista hasta que se encuentre ordenada. En el caso promedio, cada pasada por el algoritmo bogosort examinará uno de los $n!$ órdenes de la $n$ elementos. Si los elementos son distintos, solo se ordena uno de esos ordenamientos. Bogosort comparte herencia con el teorema del mono infinito .

Tiempo exponencial doble

Se dice que un algoritmo tiene un tiempo exponencial doble si $T(n)$ está limitado superiormente por $2^{2^{{\text{poly}}(n)}}$ , dónde ${\text{poly}}(n)$ es algún polinomio en $n$ . Dichos algoritmos pertenecen a la clase de complejidad 2-EXPTIME .

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

Entre los algoritmos de tiempo exponencial doble más conocidos se incluyen:

Procedimientos de decisión para la aritmética de Presburger
Cálculo de una base de Gröbner (en el peor de los casos ^{[ 27 ]} )
La eliminación de cuantificadores en campos cerrados reales requiere al menos el doble de tiempo exponencial, ^{[ 28 ]} y puede hacerse en este tiempo. ^{[ 29 ]}

Véase también

Referencias

1 2 Sipser, Michael (2006). Introducción a la teoría de la computación . Course Technology Inc. ISBN 0-619-21764-2.
↑ Mehlhorn, Kurt ; Naher, Stefan (1990). "Diccionarios ordenados acotados en $O(\log \log N)$ tiempo y $O(n)$ espacio". Information Processing Letters . 35 (4): 183– 189. doi : 10.1016/0020-0190(90)90022-P .
↑ Tao, Terence (2010). "1.11 La prueba de primalidad AKS" . Un épsilon de espacio, II: Páginas del tercer año de un blog matemático . Estudios de posgrado en matemáticas. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86 . doi : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4. MR 2780010 .
↑ Lenstra, HW Jr. ; Pomerance, Carl (2019). "Prueba de primalidad con períodos gaussianos" (PDF) . Journal of the European Mathematical Society . 21 (4): 1229– 1269. doi : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 . MR 3941463 . S2CID 127807021 .
↑ Calude, Cristian S. y Jain, Sanjay y Khoussainov, Bakhadyr y Li, Wei y Stephan, Frank (2017). "Decidiendo juegos de paridad en tiempo cuasipolinomial" . Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Association for Computing Machinery. págs. 252–263 . doi : 10.1145/3055399.3055409 . hdl : 2292/31757 . ISBN 9781450345286. S2CID 30338402 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
1 2 Babai, László ; Fortnow, Lance ; Nisan, N .; Wigderson, Avi (1993). "BPP tiene simulaciones de tiempo subexponencial a menos que EXPTIME tenga pruebas publicables". Complejidad Computacional . 3 (4). Berlín, Nueva York: Springer-Verlag : 307–318 . doi : 10.1007/BF01275486 . S2CID 14802332 .
↑ Bradford, Phillip G.; Rawlins, Gregory JE; Shannon, Gregory E. (1998). "Ordenación eficiente de cadenas de matrices en tiempo polilogarítmico". SIAM Journal on Computing . 27 (2): 466– 490. doi : 10.1137/S0097539794270698 . MR 1616556 .
↑ Holm, Jacob; Rotenberg, Eva (2020). "Prueba de planaridad totalmente dinámica en tiempo polilogarítmico". En Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). Actas del 52.º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2020, Chicago, IL, EE. UU., 22-26 de junio de 2020. Association for Computing Machinery. págs. 167–180 . arXiv : 1911.03449 . doi : 10.1145/3357713.3384249 . ISBN 978-1-4503-6979-4.
↑ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Algoritmos de tiempo sublineal" (PDF) . SIGACT News . 34 (4): 57– 67. doi : 10.1145/954092.954103 . S2CID 65359 .
↑ Rubinfeld, Ronitt (2019). «Algoritmos de computación local». Actas del Simposio ACM de 2019 sobre Principios de Computación Distribuida . pág. 3. doi : 10.1145/3293611.3331587 . ISBN 978-1-4503-6217-7.
↑ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "Sobre la teoría de la complejidad temporal cuasilineal" (PDF) . Theoretical Computer Science . 148 (2): 325– 349. doi : 10.1016/0304-3975(95)00031-Q . MR 1355592 .
↑ Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4.ª ed.). Pearson Education. pág. 186.
↑ Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
↑ Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Actas de Lógica, Metodología y Filosofía de la Ciencia II . North Holland.
↑ Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "Dureza ETH para los más densos- $k$ -subgrafo con completitud perfecta". En Klein, Philip N. (ed.). Actas del Vigésimo Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA 2017, Barcelona, España, Hotel Porta Fira, 16-19 de enero . Sociedad de Matemáticas Industriales y Aplicadas. pp. 1326–1341 . arXiv : 1504.08352 . doi : 10.1137/1.9781611974782.86 . ISBN 978-1-61197-478-2MR 3627815 .
↑ Complexity Zoo : Clase QP: Tiempo cuasipolinomial
1 2 Impagliazzo, Russell ; Paturi, Ramamohan (2001). "Sobre la complejidad de $k$ -SAT" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 62 (2): 367– 375. doi : 10.1006/jcss.2000.1727 . MR 1820597 .
↑ Aaronson, Scott (5 de abril de 2009). "Un dilema no del todo exponencial" . Shtetl-Optimized . Consultado el 2 de diciembre de 2009 .
↑ Complexity Zoo : Clase SUBEXP: Tiempo subexponencial determinista
↑ Moser, P. (2003). "Las categorías de Baire en clases de complejidad pequeña". En Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentos de la teoría de la computación: 14.º Simposio Internacional, FCT 2003, Malmö, Suecia, 12-15 de agosto de 2003, Actas . Lecture Notes in Computer Science . Vol. 2751. Berlín, Nueva York: Springer-Verlag. pp. 333–342 . doi : 10.1007/978-3-540-45077-1_31 . ISBN 978-3-540-40543-6ISSN 0302-9743
↑ Miltersen, PB (2001). "Desrandomizing Complexity Classes". Handbook of Randomized Computing . Combinatorial Optimization. Vol. 9. Kluwer Academic Pub. p. 843. doi : 10.1007/978-1-4615-0013-1_19 (inactivo el 21 de julio de 2025). ISBN 978-1-4613-4886-3.{{cite book}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
↑ Kuperberg, Greg (2005). "Un algoritmo cuántico de tiempo subexponencial para el problema del subgrupo oculto diedral". SIAM Journal on Computing . 35 (1). Filadelfia: 188. arXiv : quant-ph/0302112 . doi : 10.1137/s0097539703436345 . ISSN 1095-7111 . S2CID 15965140 .
↑ Oded Regev (2004). "Un algoritmo de tiempo subexponencial para el problema del subgrupo oculto diedral con espacio polinomial". arXiv : quant-ph/0406151v1 .
↑ Grohe, Martin; Neuen, Daniel (2021). "Avances recientes en el problema del isomorfismo de grafos". En Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniël (eds.). Surveys in combinatorics 2021. London Mathematical Society Lecture Note Series. Vol. 470. Cambridge University Press. pp. 187–234 . arXiv : 2011.01366 . ISBN 978-1-009-01888-3. MR 4273431 .
↑ Flum, Jörg; Grohe, Martín (2006). Teoría de la Complejidad Parametrizada . Saltador. pag. 417.ISBN 978-3-540-29952-3.
↑ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "¿Qué problemas tienen una complejidad fuertemente exponencial?" . Journal of Computer and System Sciences . 63 (4): 512– 530. doi : 10.1006/jcss.2001.1774 .
↑ Mayr, Ernst W. ; Meyer, Albert R. (1982). "La complejidad de los problemas de palabras para semigrupos conmutativos e ideales polinomiales" . Advances in Mathematics . 46 (3): 305– 329. doi : 10.1016/0001-8708(82)90048-2 . hdl : 1721.1/149010 . MR 0683204 .
↑ Davenport, James H. ; Heintz, Joos (1988). "La eliminación de cuantificadores reales es doblemente exponencial" . Journal of Symbolic Computation . 5 ( 1– 2): 29– 35. doi : 10.1016/S0747-7171(88)80004-X . MR 0949111 .
↑ Collins, George E. (1975). "Eliminación de cuantificadores para campos reales cerrados mediante descomposición algebraica cilíndrica". En Brakhage, H. (ed.). Teoría de autómatas y lenguajes formales: 2.ª Conferencia GI, Kaiserslautern, 20-23 de mayo de 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134-183 . doi : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6MR 0403962 .

[Sipser-1] 1 2 Sipser, Michael (2006). Introducción a la teoría de la computación . Course Technology Inc. ISBN 0-619-21764-2.

[2] Mehlhorn, Kurt ; Naher, Stefan (1990). "Diccionarios ordenados acotados en $O(\log \log N)$ tiempo y $O(n)$ espacio". Information Processing Letters . 35 (4): 183– 189. doi : 10.1016/0020-0190(90)90022-P .

[tao-aks-3] Tao, Terence (2010). "1.11 La prueba de primalidad AKS" . Un épsilon de espacio, II: Páginas del tercer año de un blog matemático . Estudios de posgrado en matemáticas. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86 . doi : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4. MR 2780010 .

[4] Lenstra, HW Jr. ; Pomerance, Carl (2019). "Prueba de primalidad con períodos gaussianos" (PDF) . Journal of the European Mathematical Society . 21 (4): 1229– 1269. doi : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 . MR 3941463 . S2CID 127807021 .

[5] Calude, Cristian S. y Jain, Sanjay y Khoussainov, Bakhadyr y Li, Wei y Stephan, Frank (2017). "Decidiendo juegos de paridad en tiempo cuasipolinomial" . Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Association for Computing Machinery. págs. 252–263 . doi : 10.1145/3055399.3055409 . hdl : 2292/31757 . ISBN 9781450345286. S2CID 30338402 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

[bpp-6] 1 2 Babai, László ; Fortnow, Lance ; Nisan, N .; Wigderson, Avi (1993). "BPP tiene simulaciones de tiempo subexponencial a menos que EXPTIME tenga pruebas publicables". Complejidad Computacional . 3 (4). Berlín, Nueva York: Springer-Verlag : 307–318 . doi : 10.1007/BF01275486 . S2CID 14802332 .

[7] Bradford, Phillip G.; Rawlins, Gregory JE; Shannon, Gregory E. (1998). "Ordenación eficiente de cadenas de matrices en tiempo polilogarítmico". SIAM Journal on Computing . 27 (2): 466– 490. doi : 10.1137/S0097539794270698 . MR 1616556 .

[8] Holm, Jacob; Rotenberg, Eva (2020). "Prueba de planaridad totalmente dinámica en tiempo polilogarítmico". En Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). Actas del 52.º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2020, Chicago, IL, EE. UU., 22-26 de junio de 2020. Association for Computing Machinery. págs. 167–180 . arXiv : 1911.03449 . doi : 10.1145/3357713.3384249 . ISBN 978-1-4503-6979-4.

[9] Kumar, Ravi; Rubinfeld, Ronitt (2003). "Algoritmos de tiempo sublineal" (PDF) . SIGACT News . 34 (4): 57– 67. doi : 10.1145/954092.954103 . S2CID 65359 .

[10] Rubinfeld, Ronitt (2019). «Algoritmos de computación local». Actas del Simposio ACM de 2019 sobre Principios de Computación Distribuida . pág. 3. doi : 10.1145/3293611.3331587 . ISBN 978-1-4503-6217-7.

[11] Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "Sobre la teoría de la complejidad temporal cuasilineal" (PDF) . Theoretical Computer Science . 148 (2): 325– 349. doi : 10.1016/0304-3975(95)00031-Q . MR 1355592 .

[12] Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4.ª ed.). Pearson Education. pág. 186.

[13] Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.

[14] Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Actas de Lógica, Metodología y Filosofía de la Ciencia II . North Holland.

[15] Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "Dureza ETH para los más densos- $k$ -subgrafo con completitud perfecta". En Klein, Philip N. (ed.). Actas del Vigésimo Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA 2017, Barcelona, España, Hotel Porta Fira, 16-19 de enero . Sociedad de Matemáticas Industriales y Aplicadas. pp. 1326–1341 . arXiv : 1504.08352 . doi : 10.1137/1.9781611974782.86 . ISBN 978-1-61197-478-2MR 3627815 .

[16] Complexity Zoo : Clase QP: Tiempo cuasipolinomial

[ETH-17] 1 2 Impagliazzo, Russell ; Paturi, Ramamohan (2001). "Sobre la complejidad de $k$ -SAT" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 62 (2): 367– 375. doi : 10.1006/jcss.2000.1727 . MR 1820597 .

[18] Aaronson, Scott (5 de abril de 2009). "Un dilema no del todo exponencial" . Shtetl-Optimized . Consultado el 2 de diciembre de 2009 .

[19] Complexity Zoo : Clase SUBEXP: Tiempo subexponencial determinista

[20] Moser, P. (2003). "Las categorías de Baire en clases de complejidad pequeña". En Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentos de la teoría de la computación: 14.º Simposio Internacional, FCT 2003, Malmö, Suecia, 12-15 de agosto de 2003, Actas . Lecture Notes in Computer Science . Vol. 2751. Berlín, Nueva York: Springer-Verlag. pp. 333–342 . doi : 10.1007/978-3-540-45077-1_31 . ISBN 978-3-540-40543-6ISSN 0302-9743

[21] Miltersen, PB (2001). "Desrandomizing Complexity Classes". Handbook of Randomized Computing . Combinatorial Optimization. Vol. 9. Kluwer Academic Pub. p. 843. doi : 10.1007/978-1-4615-0013-1_19 (inactivo el 21 de julio de 2025). ISBN 978-1-4613-4886-3.{{cite book}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )

[22] Kuperberg, Greg (2005). "Un algoritmo cuántico de tiempo subexponencial para el problema del subgrupo oculto diedral". SIAM Journal on Computing . 35 (1). Filadelfia: 188. arXiv : quant-ph/0302112 . doi : 10.1137/s0097539703436345 . ISSN 1095-7111 . S2CID 15965140 .

[23] Oded Regev (2004). "Un algoritmo de tiempo subexponencial para el problema del subgrupo oculto diedral con espacio polinomial". arXiv : quant-ph/0406151v1 .

[24] Grohe, Martin; Neuen, Daniel (2021). "Avances recientes en el problema del isomorfismo de grafos". En Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniël (eds.). Surveys in combinatorics 2021. London Mathematical Society Lecture Note Series. Vol. 470. Cambridge University Press. pp. 187–234 . arXiv : 2011.01366 . ISBN 978-1-009-01888-3. MR 4273431 .

[25] Flum, Jörg; Grohe, Martín (2006). Teoría de la Complejidad Parametrizada . Saltador. pag. 417.ISBN 978-3-540-29952-3.

[26] Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "¿Qué problemas tienen una complejidad fuertemente exponencial?" . Journal of Computer and System Sciences . 63 (4): 512– 530. doi : 10.1006/jcss.2001.1774 .

[27] Mayr, Ernst W. ; Meyer, Albert R. (1982). "La complejidad de los problemas de palabras para semigrupos conmutativos e ideales polinomiales" . Advances in Mathematics . 46 (3): 305– 329. doi : 10.1016/0001-8708(82)90048-2 . hdl : 1721.1/149010 . MR 0683204 .

[28] Davenport, James H. ; Heintz, Joos (1988). "La eliminación de cuantificadores reales es doblemente exponencial" . Journal of Symbolic Computation . 5 ( 1– 2): 29– 35. doi : 10.1016/S0747-7171(88)80004-X . MR 0949111 .

[29] Collins, George E. (1975). "Eliminación de cuantificadores para campos reales cerrados mediante descomposición algebraica cilíndrica". En Brakhage, H. (ed.). Teoría de autómatas y lenguajes formales: 2.ª Conferencia GI, Kaiserslautern, 20-23 de mayo de 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134-183 . doi : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6MR 0403962 .

[ 1 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 6 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]