Complejidad temporal

Estimación del tiempo necesario para ejecutar un algoritmo

Gráficos 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 que tarda un ordenador en 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 para realizarse. Por tanto, se supone que la cantidad de tiempo empleado y el número de operaciones elementales que realiza 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, uno comúnmente considera la complejidad temporal del peor caso , que es la cantidad máxima de tiempo requerida para entradas de un tamaño dado. Menos común, y usualmente especificada explícitamente, es la complejidad del caso promedio , que es el promedio del tiempo tomado en entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de entradas posibles 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 es generalmente difícil de calcular exactamente, y el tiempo de ejecución para entradas pequeñas usualmente no es consecuente, uno comúnmente se enfoca en el comportamiento de la complejidad cuando el tamaño de entrada aumenta, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando notación O grande , típicamente , , , , etc., donde n es el tamaño en unidades de bits necesarios para representar la entrada. ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{\alpha })}$ ${\displaystyle O(2^{n})}$

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

Tabla de complejidades temporales comunes

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

Tiempo constante

Se dice que un algoritmo es de tiempo constante (también escrito como tiempo) si el valor de (la complejidad del algoritmo) está limitado por un valor que no depende del tamaño de la entrada. Por ejemplo, acceder a cualquier elemento individual en una matriz lleva un tiempo constante ya que solo se debe realizar una operación para localizarlo. De manera similar, encontrar el valor mínimo en una matriz ordenada en orden ascendente; es el primer elemento. Sin embargo, encontrar el valor mínimo en una matriz desordenada no es una operación de tiempo constante ya que se necesita escanear cada elemento de la matriz para determinar el valor mínimo. Por lo tanto, es una operación de tiempo lineal, que lleva tiempo. Sin embargo, si el número de elementos se conoce de antemano y no cambia, se puede decir que dicho algoritmo todavía se ejecuta en tiempo constante. ${\textstyle O(1)}$ ${\textstyle T(n)}$ ${\textstyle O(n)}$

A pesar del nombre de "tiempo constante", el tiempo de ejecución no tiene por qué ser independiente del tamaño del problema, pero un límite superior para el tiempo de ejecución tiene que ser independiente del tamaño del problema. Por ejemplo, la tarea "intercambiar los valores de a y b si es necesario de modo que " se llama tiempo constante aunque el tiempo puede depender de si ya es cierto o no que . Sin embargo, existe una constante t tal que el tiempo requerido es siempre como máximo t . ${\textstyle a\leq b}$ ${\textstyle a\leq b}$

Tiempo logarítmico

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

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

Un algoritmo se considera altamente eficiente cuando 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 tardar un tiempo logarítmico, ya que el tiempo que tarda en leer una entrada de tamaño n es del orden de n . ${\displaystyle O(\log n)}$

Un ejemplo de tiempo logarítmico lo da la búsqueda en un diccionario. Consideremos un diccionario D que contiene n entradas, ordenadas en orden alfabético . Supongamos que, para , se puede acceder a la k ésima entrada del diccionario en un tiempo constante. Sea , esta k ésima entrada. Bajo estas hipótesis, la prueba para ver si una palabra w está en el diccionario se puede hacer en tiempo logarítmico: considere , donde denota la función de piso . Si --es decir, la palabra w está exactamente en el medio del diccionario-- entonces hemos terminado. De lo contrario, si --es decir, si la palabra w viene antes en orden alfabético que la palabra del medio de todo el diccionario-- continuamos la búsqueda de la misma manera en la mitad izquierda (es decir, antes) del diccionario, y luego de nuevo repetidamente hasta que se encuentre la palabra correcta. De lo contrario, si viene después de la palabra del medio, continuamos de manera similar con la mitad derecha del diccionario. Este algoritmo es similar al método que se usa a menudo para encontrar una entrada en un diccionario de papel. Como resultado, el espacio de búsqueda dentro del diccionario disminuye a medida que el algoritmo se acerca a la palabra objetivo. ${\displaystyle 1\leq k\leq n}$ ${\displaystyle D(k)}$ ${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$ ${\displaystyle \lfloor \;\rfloor }$ ${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$ ${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$

Tiempo polilogarítmico

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

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

Tiempo sublineal

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

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

Otras configuraciones en las 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 una matriz ordenada.
• Algoritmos que buscan una estructura local en la entrada, por ejemplo, encontrar un mínimo local en una matriz unidimensional (se puede resolver en  el tiempo utilizando una variante de búsqueda binaria). Un concepto estrechamente relacionado es el de algoritmos de computación local (LCA), en el que el algoritmo recibe una entrada grande y consulta información local sobre una salida grande válida. ^[10] ${\displaystyle O(\log(n))}$

Tiempo lineal

Se dice que un algoritmo toma un tiempo lineal , o tiempo, si su complejidad temporal es . De manera informal, esto significa que el tiempo de ejecución aumenta como máximo de manera lineal con el tamaño de la entrada. Más precisamente, esto significa que existe una constante c tal que el tiempo de ejecución es como máximo 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á acotado por una constante. ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle cn}$

El tiempo lineal es la mejor complejidad temporal posible en situaciones en las que el algoritmo tiene que leer secuencialmente toda su entrada. Por lo tanto, se ha invertido mucha investigación en descubrir algoritmos que presenten un tiempo lineal o, al menos, un tiempo casi lineal. Esta investigación incluye métodos tanto de software como de hardware. Existen varias tecnologías de hardware que explotan el paralelismo para proporcionar esto. Un ejemplo es la memoria direccionable por contenido . Este concepto de tiempo lineal se utiliza en algoritmos de coincidencia 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 log-lineal ) si para alguna constante positiva k ; ^[11] el tiempo linealítmico es el caso . ^[12] Usando la notación O suave estos algoritmos son . Los algoritmos de tiempo cuasilineal también son para cada constante 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 para cualquier . ${\displaystyle T(n)=O(n\log ^{k}n)}$ ${\displaystyle k=1}$ ${\displaystyle {\tilde {O}}(n)}$ ${\displaystyle O(n^{1+\varepsilon })}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n^{c}}$ ${\displaystyle c>1}$

Los algoritmos que se ejecutan en tiempo cuasilineal incluyen:

• Ordenación por fusión en el lugar , ${\displaystyle O(n\log ^{2}n)}$
• Quicksort , en su versión aleatoria, tiene un tiempo de ejecución que se calcula en función de la entrada del peor caso. Su versión no aleatoria tiene un tiempo de ejecución solo cuando se considera la complejidad promedio del caso. ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$
• Heapsort , , merge sort , introsort , binary tree sort, smoothsort , patient sort , etc. en el peor de los casos ${\displaystyle O(n\log n)}$
• Transformadas rápidas de Fourier , ${\displaystyle O(n\log n)}$
• Cálculo de matriz Monge , ${\displaystyle O(n\log n)}$

En muchos casos, el tiempo de ejecución es simplemente el resultado de realizar una operación n veces (para la notación, consulte Notación Big O § Familia de notaciones de Bachmann–Landau ). Por ejemplo, la ordenación de árbol binario crea un árbol binario insertando cada elemento de la matriz de tamaño n uno por uno. Dado que la operación de inserción en un árbol binario de búsqueda autoequilibrado lleva tiempo, todo el algoritmo lleva tiempo. ${\displaystyle O(n\log n)}$ ${\displaystyle \Theta (\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n\log n)}$

Los ordenamientos por comparación requieren al menos comparaciones en el peor de los casos porque , según la aproximación de Stirling , también surgen con frecuencia de la relación de recurrencia . ${\displaystyle \Omega (n\log n)}$ ${\displaystyle \log(n!)=\Theta (n\log n)}$ ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

Tiempo subcuadrático

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

Por ejemplo, los algoritmos de ordenamiento simples basados ​​en comparaciones son cuadráticos (por ejemplo, el ordenamiento por inserción ), pero se pueden encontrar algoritmos más avanzados que son subcuadráticos (por ejemplo, el ordenamiento por capas ). No hay ordenamientos de propósito general que se ejecuten en tiempo lineal, pero el cambio de cuadrático a subcuadrático es de 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, T ( n ) = O ( n ^k ) para alguna constante positiva k . ^{[1] [13]} Los problemas para los que existe un algoritmo de tiempo polinomial determinista pertenecen a la clase de complejidad P , que es central 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 ordenamiento por selección sobre n números enteros realiza operaciones para una constante A. Por lo tanto, se ejecuta en el tiempo y es un algoritmo de tiempo polinomial. ${\displaystyle An^{2}}$ ${\displaystyle 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.
• Las máximas coincidencias en los gráficos se pueden encontrar en tiempo polinomial. En algunos contextos, especialmente en optimización , se diferencia entre algoritmos de tiempo fuertemente polinomial y algoritmos de tiempo débilmente polinomial .

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

Clases de complejidad

El concepto de tiempo polinómico da lugar a varias clases de complejidad en la teoría de la complejidad computacional. Algunas clases importantes definidas mediante el tiempo polinómico son las siguientes.

• P : La clase de complejidad de los problemas de decisión que se pueden resolver en una máquina de Turing determinista en tiempo polinomial.
• NP : La clase de complejidad de los problemas de decisión que se pueden resolver 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 un 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 un error bilateral en una máquina de Turing probabilística en tiempo polinomial.
• BQP : La clase de complejidad de los problemas de decisión que se pueden resolver con un 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 máquina de múltiples cintas puede llevar a una aceleración cuadrática, pero cualquier algoritmo que se ejecuta en tiempo polinomial bajo un modelo también lo hace en el otro). Cualquier máquina abstracta dada tendrá una clase de complejidad correspondiente a los problemas que se pueden resolver en tiempo polinomial en esa máquina.

Tiempo superpolinomial

Se define que un algoritmo toma tiempo superpolinomial si T ( n ) no está acotado por encima de ningún polinomio. Usando la notación omega pequeña , es tiempo ω ( n ^c ) para todas las constantes c , donde n es el parámetro de entrada, típicamente el número de bits en la entrada.

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

Un algoritmo que utiliza recursos exponenciales es claramente superpolinómico, pero algunos algoritmos son sólo muy débilmente superpolinómicos. Por ejemplo, la prueba de primalidad de Adleman–Pomerance–Rumely se ejecuta durante n ^{O (log log n )} tiempo en entradas de n bits; esto crece más rápido que cualquier polinomio para un valor n suficientemente grande , pero el tamaño de entrada debe volverse imprácticamente grande antes de que no pueda ser dominado por un polinomio con un grado pequeño.

Un algoritmo que requiere tiempo superpolinomial se encuentra 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 cuasi-polinomial

Los algoritmos de tiempo cuasi-polinomial son algoritmos cuyo tiempo de ejecución exhibe un crecimiento cuasi-polinomial , un tipo de comportamiento que puede ser más lento que el tiempo polinomial pero, sin embargo, es significativamente más rápido que el tiempo exponencial . El peor caso de tiempo de ejecución de un algoritmo de tiempo cuasi-polinomial es para un valor fijo . Cuando esto da un tiempo polinomial, y para da un tiempo sub-lineal. ${\displaystyle 2^{O(\log ^{c}n)}}$ ${\displaystyle c>0}$ ${\displaystyle c=1}$ ${\displaystyle c<1}$

Existen algunos problemas para los cuales conocemos algoritmos de tiempo cuasi-polinomial, pero no se conoce ningún algoritmo de tiempo polinomial. Tales 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 cuasi-polinomial que logra un factor de aproximación de ( siendo n el número de vértices), pero demostrar la existencia de tal algoritmo de tiempo polinomial es un problema abierto. ${\displaystyle O(\log ^{3}n)}$

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

La clase de complejidad QP está formada por todos los problemas que tienen algoritmos de tiempo cuasi-polinomial. Puede definirse en términos de DTIME de la siguiente manera. ^[16]

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

Relación con problemas NP-completos

En teoría de la complejidad, el problema no resuelto P versus NP plantea la pregunta de 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 que muchos problemas NP-completos naturales no tienen algoritmos de tiempo subexponencial. Aquí, "tiempo subexponencial" se entiende como la segunda definición que se presenta a continuación. (Por otro lado, muchos problemas de grafos representados de forma natural 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 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 parten del supuesto de 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 expresar que el tiempo de ejecución de algún algoritmo puede crecer más rápido que cualquier polinomio, pero sigue siendo significativamente menor que un exponencial. En este sentido, los problemas que tienen algoritmos de tiempo subexponencial son algo más manejables que aquellos que solo tienen algoritmos exponenciales. La definición precisa de "subexponencial" no es generalmente aceptada, ^[18] sin embargo, las dos más utilizadas son las siguientes.

Primera definición

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

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

Esta noción de subexponencial no es uniforme en términos de ε en el sentido de que ε no es 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 . ^{[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 de este tipo es el algoritmo clásico más conocido para la factorización de enteros, el tamiz de campo numérico general , que se ejecuta en un tiempo alrededor de , donde la longitud de la entrada es n . Otro ejemplo fue el problema de isomorfismo de grafos , que el algoritmo más conocido desde 1982 hasta 2016 resolvió en . Sin embargo, en STOC 2016 se presentó un algoritmo de tiempo cuasipolinomial. ^[24] ${\displaystyle 2^{o(n)}}$ ${\displaystyle 2^{{\tilde {O}}(n^{1/3})}}$ ${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$

Hay una diferencia 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 de problemas de decisión y parámetros k . SUBEPT es la clase de todos los problemas parametrizados que se ejecutan en un tiempo subexponencial en k y polinomial en el tamaño de entrada n : ^[25] ${\displaystyle (L,k)}$

${\displaystyle {\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 con y un algoritmo que decide L en el tiempo . ${\displaystyle (L,k)}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f\in o(k)}$ ${\displaystyle 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 en el tiempo 2 ^{o ( n )} . Más precisamente, la hipótesis es que hay alguna constante absoluta c > 0 tal que 3SAT no se puede decidir en el tiempo 2 ^cn por ninguna máquina de Turing determinista. Con m denotando el número de cláusulas, ETH es equivalente a la hipótesis de que k SAT no se puede resolver en el tiempo 2 ^{o ( m )} para cualquier entero k ≥ 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á acotado superiormente por 2 ^{poly( n )} , donde poly( n ) es algún polinomio en n . Más formalmente, un algoritmo es de tiempo exponencial si T ( n ) está acotado por O (2 ^{n k} ) para 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 .

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

En ocasiones, se utiliza el tiempo exponencial 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.

${\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{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 para todo . Sin embargo, no es un subconjunto de E. ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$ ${\displaystyle \epsilon >0}$

Un ejemplo de un algoritmo que se ejecuta en tiempo factorial es bogosort , un algoritmo de ordenamiento notoriamente ineficiente basado en prueba y error . Bogosort ordena una lista de n elementos barajando repetidamente la lista hasta que se descubre que está ordenada. En el caso promedio, cada pasada a través del algoritmo bogosort examinará uno de los n ! ordenamientos de los n elementos. Si los elementos son distintos, solo se ordena uno de esos ordenamientos. Bogosort comparte patrimonio con el teorema del mono infinito .

Tiempo exponencial doble

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

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

Los algoritmos de tiempo exponencial doble más conocidos 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 del cuantificador en campos cerrados reales requiere al menos el doble del tiempo exponencial ^[28] y se puede realizar en este tiempo. ^[29]

Véase también

• Notación L
• Complejidad espacial

Referencias

1. 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 tiempo O (log log N ) y espacio O ( n ) ". Cartas de procesamiento de la información . 35 (4): 183–189. doi :10.1016/0020-0190(90)90022-P.
3. Tao, Terence (2010). "1.11 La prueba de primalidad AKS". Un épsilon de la habitación, 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. págs. 82–86. doi :10.1090/gsm/117. ISBN. 978-0-8218-5280-4.Señor 2780010  .
4. Lenstra, HW Jr. ; Pomerance, Carl (2019). "Pruebas de primalidad con periodos gaussianos" (PDF) . Revista de la Sociedad Matemática Europea . 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). "Decidir 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. Número de identificación del sujeto  30338402.{{cite book}}: CS1 maint: multiple names: authors list (link)
6. 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). "Ordenamiento 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). "Pruebas de planaridad completamente dinámicas 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 (PODC) . p. 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 en tiempo 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". Proc. Lógica, metodología y filosofía de la ciencia II . Holanda Septentrional.
15. Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "Dureza ETH para el subgrafo k más denso 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. págs. 1326–1341. arXiv : 1504.08352 . doi :10.1137/1.9781611974782.86. ISBN 978-1-61197-478-2.Señor 3627815  .
16. Complexity Zoo : Clase QP: Tiempo cuasipolinomial
17. 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). "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 . Apuntes de clase en informática . Vol. 2751. Berlín, Nueva York: Springer-Verlag. págs. 333–342. doi :10.1007/978-3-540-45077-1_31. ISBN . 978-3-540-40543-6. ISSN  0302-9743.
21. Miltersen, PB (2001). "Desrandomización de clases de complejidad". Manual de computación aleatoria . Optimización combinatoria. 9. Kluwer Academic Pub: 843. doi :10.1007/978-1-4615-0013-1_19 (inactivo el 18 de marzo de 2024). ISBN 978-1-4613-4886-3.{{cite journal}}: CS1 maint: DOI inactive as of March 2024 (link)
22. Kuperberg, Greg (2005). "Un algoritmo cuántico de tiempo subexponencial para el problema del subgrupo oculto diedral". Revista SIAM de informática . 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.). Encuestas en combinatoria 2021 . Serie de notas de conferencias de la London Mathematical Society. Vol. 470. Cambridge University Press. págs. 187–234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3.Señor 4273431  .
25. Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada. Springer. pág. 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 verbales para semigrupos conmutativos e ideales polinomiales". Avances en Matemáticas . 46 (3): 305–329. doi : 10.1016/0001-8708(82)90048-2 . MR  0683204.
28. Davenport, James H. ; Heintz, Joos (1988). "La eliminación del cuantificador real 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 de GI, Kaiserslautern, 20-23 de mayo de 1975. Lecture Notes in Computer Science. Vol. 33. Springer. págs. 134-183. doi : 10.1007/3-540-07407-4_17 . ISBN . 978-3-540-07407-6.Sr. 0403962  .