Complejidad del tiempo

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 del tiempo es la complejidad computacional que describe la cantidad de tiempo de computadora que se necesita para ejecutar un algoritmo . La complejidad del tiempo se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad de tiempo fija para realizarse. Por tanto, la cantidad de tiempo necesaria y el número de operaciones elementales realizadas por el algoritmo se consideran relacionados mediante 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 del tiempo en el peor de los casos , que es la cantidad máxima de tiempo requerida para entradas de un tamaño determinado. Menos común, y generalmente especificada explícitamente, es la complejidad de caso promedio , que es el promedio del tiempo necesario para las entradas de un tamaño determinado (esto tiene sentido porque solo hay un número finito de entradas posibles de un tamaño determinado). En ambos casos, la complejidad temporal generalmente se expresa como función del tamaño de la entrada. ^{[1] : 226} Dado que esta función generalmente es difícil de calcular exactamente y el tiempo de ejecución para entradas pequeñas generalmente no tiene consecuencias, comúnmente uno se enfoca en el comportamiento de la complejidad cuando el tamaño de la entrada aumenta, es decir, el comportamiento asintótico de la función . complejidad. Por lo tanto , la complejidad del tiempo 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 grande. 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 >1}$

Tabla de complejidades horarias comunes

La siguiente tabla resume algunas clases de complejidades de tiempo que se encuentran comúnmente. En la tabla, poli( 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 de una matriz requiere un tiempo constante, ya que solo es necesario 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 es necesario escanear cada elemento de la matriz para determinar el valor mínimo. Por tanto, es una operación de tiempo lineal, que requiere tiempo. Sin embargo, si el número de elementos se conoce de antemano y no cambia, aún se puede decir que dicho algoritmo se ejecuta en tiempo constante. ${\textstyle O(1)}$ ${\textstyle T(n)}$ ${\textstyle O(n)}$

A pesar del nombre "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 para 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 siempre es 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 de los 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, 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 un tiempo logarítmico, ya que el tiempo necesario para leer una entrada de tamaño n es del orden de n . ${\displaystyle O(\log n)}$

La búsqueda en un diccionario proporciona un ejemplo de tiempo logarítmico. Considere 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. Denotemos esta késima entrada. Bajo estas hipótesis, la prueba para ver si una palabra w está en el diccionario se puede realizar en tiempo logarítmico: considere , donde denota la función suelo . 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 aparece 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 nuevamente repetidamente hasta encontrar la palabra correcta. De lo contrario, si viene después de la palabra del medio, continúe de manera similar con la mitad derecha del diccionario. Este algoritmo es similar al método que se utiliza a menudo para buscar una entrada en un diccionario en 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 alguna 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 cadenas de matrices se puede resolver en tiempo polilogarítmico en una máquina paralela de acceso aleatorio , ^[7] y se puede determinar que un gráfico es plano 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 comúnmente se refiere a algoritmos aleatorios que muestrean 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 donde los algoritmos pueden ejecutarse en tiempo sublineal incluyen:

• Algoritmos paralelos que tienen un trabajo total lineal o mayor (lo que les permite leer la entrada completa), 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 1-D (se puede resolver a  tiempo usando una variante de búsqueda binaria). Una noción estrechamente relacionada es la de algoritmos de computación local (LCA), donde el algoritmo recibe una gran entrada y consulta información local sobre alguna salida grande válida. ^[10] ${\displaystyle O(\log(n))}$

tiempo lineal

Se dice que un algoritmo toma tiempo lineal , o tiempo, si su complejidad temporal es . Informalmente, 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 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á limitado 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 investigado mucho para descubrir algoritmos que muestren 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 conocido como tiempo log-lineal ) si para alguna constante positiva k ; ^[11] el tiempo linealítmico es el caso . ^[12] Usando 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 polinómico cuyo límite de tiempo incluya un término para cualquiera . ${\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:

• Clasificación por combinación in situ , ${\displaystyle O(n\log ^{2}n)}$
• Quicksort , en su versión aleatoria, tiene un tiempo de ejecución esperado en la entrada del peor de los casos. Su versión no aleatoria tiene un tiempo de ejecución sólo 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 , paciencia sorting , 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 conocer la notación, consulte Notación O grande § Familia de notaciones Bachmann-Landau ). Por ejemplo, la clasificació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 de búsqueda binario 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 tipos de comparación requieren al menos comparaciones en el peor de los casos porque , según la aproximación de Stirling . También surgen frecuentemente 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 clasificación simples basados ​​en comparaciones son cuadráticos (por ejemplo, clasificación por inserción ), pero se pueden encontrar algoritmos más avanzados que son subcuadráticos (por ejemplo, clasificación por shell ). Ninguna clasificación de propósito general se ejecuta 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 polinómico si su tiempo de ejecución está limitado superiormente por una expresión polinómica en el tamaño de la entrada del algoritmo, es decir, T ( n ) = O ( n ^k ) para alguna constante positiva k . ^{[1] [13]} Los problemas para los cuales existe un algoritmo determinista de tiempo polinomial 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 clasificación de selección en n enteros realiza operaciones para alguna constante A. Por 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 polinómico.
• Las coincidencias máximas en 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 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 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 los problemas de decisión que se pueden resolver con error cero en una máquina probabilística de Turing en tiempo polinomial.
• RP : La clase de complejidad de los problemas de decisión que se pueden resolver con error unilateral en una máquina probabilística de Turing en tiempo polinomial.
• BPP : la clase de complejidad de los problemas de decisión que se pueden resolver con error bilateral en una máquina probabilística de Turing en tiempo polinómico.
• BQP : la clase de complejidad de los problemas de decisión que se pueden resolver con error bilateral en una máquina cuántica de Turing 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 de modelo de 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 conducir a una aceleración cuadrática, pero cualquier algoritmo que se ejecute en tiempo polinomial bajo un modelo también lo hace en el otro.) Cualquier máquina abstracta dada tener una clase de complejidad correspondiente a los problemas que se pueden resolver en tiempo polinomial en esa máquina.

tiempo superpolinomial

Se define un algoritmo para tomar tiempo superpolinomial si T ( n ) no está acotado arriba por ningún polinomio. Usando pequeña notación omega , es ω ( n ^c ) tiempo para todas las constantes c , donde n es el parámetro de entrada, generalmente 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, un tiempo exponencial).

Un algoritmo que utiliza recursos exponenciales es claramente superpolinomial, pero algunos algoritmos son sólo muy débilmente superpolinomiales. 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 n lo suficientemente grande , pero el tamaño de entrada debe volverse imprácticamente grande antes de que no pueda ser dominado por un polinomio con 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 no son 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 exhibe un crecimiento cuasipolinomial , un tipo de comportamiento que puede ser más lento que el tiempo polinómico pero que aún así es significativamente más rápido que el tiempo exponencial . El peor de los casos de tiempo de ejecución de un algoritmo de tiempo cuasipolinomial es para algunos fijos . Cuando esto da tiempo polinómico, y para ello da tiempo sublineal. ${\displaystyle 2^{O(\log ^{c}n)}}$ ${\displaystyle c>0}$ ${\displaystyle c=1}$ ${\displaystyle c<1}$

Hay algunos problemas para los cuales conocemos algoritmos de tiempo cuasipolinomial, pero no se conoce ningún algoritmo de tiempo polinomial. Estos problemas surgen en los 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 logra un factor de aproximación de ( siendo n el número de vértices), pero mostrar la existencia de dicho algoritmo de tiempo polinómico es un problema abierto. ${\displaystyle O(\log ^{3}n)}$

Otros problemas computacionales con soluciones de tiempo cuasipolinomiales pero sin solución de tiempo polinómico conocida incluyen el problema de 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 tiene una solución casi polinomial, se ha conjeturado que el problema de la camarilla plantada no tiene solución en el tiempo polinomial; Esta conjetura de la camarilla plantada se ha utilizado como un supuesto de dureza computacional para demostrar la dificultad de varios otros problemas en la 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 cuasipolinomiales. Se puede definir en términos de DTIME de la siguiente manera. ^[dieciséis]

${\displaystyle {\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 no resuelto de P versus NP pregunta si todos los problemas en NP tienen algoritmos de tiempo polinomial. Todos los algoritmos más conocidos para problemas NP-completos como 3SAT, etc. toman un tiempo exponencial. De hecho, se conjetura que para muchos problemas NP-completos naturales no tienen algoritmos de tiempo subexponenciales. Aquí se entiende por "tiempo subexponencial" la segunda definición que se presenta a continuación. (Por otro lado, muchos problemas de gráficos 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) es conocida como hipótesis del tiempo exponencial . ^[17] Dado que se conjetura que los problemas NP-completos no tienen algoritmos de tiempo cuasipolinomiales, algunos resultados de inaproximabilidad en el campo de los algoritmos de aproximación suponen que los problemas NP-completos no tienen algoritmos de tiempo cuasipolinomiales. Por ejemplo, consulte los resultados de inaproximabilidad conocidos para el problema de cobertura del conjunto .

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 subexponenciales son algo más manejables que aquellos que solo tienen algoritmos exponenciales. En general, no existe un consenso sobre la definición precisa de "subexponencial", ^[18] sin embargo, a continuación se detallan las dos más utilizadas.

Primera definición

Se dice que un problema tiene solución en el tiempo subexponencial si se puede resolver en tiempos continuos cuyos logaritmos crecen más pequeños que cualquier polinomio dado. Más precisamente, un problema está en tiempo subexponencial si para cada ε > 0 existe un algoritmo que resuelve el problema en el 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 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 el tiempo aproximadamente , donde la longitud de la entrada es n . Otro ejemplo fue el problema del isomorfismo gráfico , que resolvió el algoritmo más conocido de 1982 a 2016 . Sin embargo, en STOC 2016 se presentó un algoritmo de tiempo cuasi polinomial. ^[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 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 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 existe una constante absoluta c > 0 tal que ninguna máquina determinista de Turing puede decidir 3SAT en el tiempo 2 ^cn . Con m denotando el número de cláusulas, ETH es equivalente a la hipótesis de que k SAT no puede resolverse en el tiempo 2 ^{o ( m )} para cualquier número 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á limitado superiormente por 2 ^{poli( n )} , donde poli( n ) es algún polinomio en n . Más formalmente, un algoritmo es ^de tiempo exponencial si T ( n ) está acotado por O (2nk ⁾ 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)}$

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.

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

tiempo factorial

Se dice que un algoritmo es 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 todos . 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 clasificación notoriamente ineficiente basado en prueba y error . Bogosort ordena una lista de n elementos barajando repetidamente la lista hasta que se encuentra que está ordenada. En el caso promedio, cada paso por el algoritmo bogosort examinará uno de los n ! ordenamiento de los n elementos. Si los elementos son distintos, sólo se clasifica un orden de ese tipo. Bogosort comparte patrimonio con el teorema del mono infinito .

Tiempo doble exponencial

Se dice que un algoritmo es de tiempo doble exponencial si T ( n ) está limitado superiormente por 2 ^{2 poli( n )} , donde poli( n ) es algún polinomio en n . Estos 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 doble exponencial más conocidos incluyen:

• Procedimientos de decisión para la aritmética de Presburger.
• Calcular 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 de tiempo exponencial ^[28] y se puede realizar en este tiempo. ^[29]

Ver también

• Notación L
• Complejidad espacial

Referencias

1. Sipser, Michael (2006). Introducción a la Teoría de la Computación . Curso Tecnología 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 información . 35 (4): 183–189. doi :10.1016/0020-0190(90)90022-P.
3. Tao, Terence (2010). "1.11 La prueba de primalidad de AKS". Una épsilon de habitación, II: Páginas del tercer año de un blog matemático . Estudios de Posgrado en Matemáticas. vol. 117. Providence, RI: Sociedad Matemática Estadounidense. págs. 82–86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4. SEÑOR  2780010.
4. Lenstra, HW Jr .; Pomerancia, Carl (2019). "Prueba de primalidad con períodos 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. SEÑOR  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 . Asociación para Maquinaria de Computación. págs. 252-263. doi :10.1145/3055399.3055409. hdl :2292/31757. ISBN 9781450345286. S2CID  30338402.{{cite book}}: CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link)
6. Babai, László ; Por ahora, Lance ; Nisan, N .; Wigderson, Avi (1993). "BPP tiene simulaciones de tiempo subexponenciales 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 polilógico". Revista SIAM de Computación . 27 (2): 466–490. doi :10.1137/S0097539794270698. SEÑOR  1616556.
8. Holm, Jacob; Rothenberg, Eva (2020). "Prueba de planaridad totalmente dinámica en tiempo polilogarítmico". En Makarychev, Konstantin; Makarychev, Yuri; 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 al 26 de junio de 2020 . Asociación para Maquinaria de Computación. 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) . Noticias SIGACT . 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 informática distribuida (PODC) . pag. 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 del tiempo cuasilineal" (PDF) . Informática Teórica . 148 (2): 325–349. doi : 10.1016/0304-3975(95)00031-Q . SEÑOR  1355592.
12. Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4ª ed.). Educación Pearson. pag. 186.
13. Papadimitriou, Christos H. (1994). Complejidad computacional . Lectura, Massachusetts: 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 del Norte.
15. Hombre valiente, Mark ; Kun-Ko, joven; Rubinstein, Aviad; Weinstein, Omri (2017). "Dureza ETH para el subgrafo k más denso con perfecta integridad". 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ática Industrial y Aplicada. 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 . SEÑOR  1820597.
18. Aaronson, Scott (5 de abril de 2009). "Un dilema no del todo exponencial". Optimizado para Shtetl . Consultado el 2 de diciembre de 2009 .
19. Complexity Zoo : Clase SUBEXP: Tiempo subexponencial determinista
20. Moser, P. (2003). "Categorías de Baire sobre clases de pequeña complejidad". En Andrzej Lingás; Bengt J. Nilsson (eds.). Fundamentos de la teoría de la computación: 14º Simposio internacional, FCT 2003, Malmö, Suecia, 12 al 15 de agosto de 2003, Actas . Apuntes de conferencias sobre 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). "Desaleatorizar las clases de complejidad". Manual de informática aleatoria . Optimización combinatoria. 9 . Pub académico Kluwer: 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 diédrico". Revista SIAM de Computación . 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 diédrico con espacio polinómico". arXiv : quant-ph/0406151v1 .
24. Grohe, Martín; Neuen, Daniel (2021). "Avances recientes en el problema del isomorfismo gráfico". En Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicolás; Johnson, Mateo; Mertzios, George B.; Paulusma, Daniël (eds.). Encuestas en combinatoria 2021 . Serie de notas de conferencias de la Sociedad Matemática de Londres. vol. 470. Prensa de la Universidad de Cambridge. págs. 187-234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3. SEÑOR  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?". Revista de Ciencias de la Computación y de Sistemas . 63 (4): 512–530. doi : 10.1006/jcss.2001.1774 .
27. Mayr, Ernst W .; Meyer, Albert R. (1982). "La complejidad de los problemas planteados para semigrupos conmutativos e ideales polinomiales". Avances en Matemáticas . 46 (3): 305–329. doi : 10.1016/0001-8708(82)90048-2 . SEÑOR  0683204.
28. Davenport, James H .; Heintz, Joos (1988). "La eliminación del cuantificador real es doblemente exponencial". Revista de Computación Simbólica . 5 (1–2): 29–35. doi : 10.1016/S0747-7171(88)80004-X . SEÑOR  0949111.
29. Collins, George E. (1975). "Eliminación de cuantificadores para campos cerrados reales mediante descomposición algebraica cilíndrica". En Brakhage, H. (ed.). Teoría de autómatas y lenguajes formales: segunda conferencia GI, Kaiserslautern, 20 al 23 de mayo de 1975 . Apuntes de conferencias sobre informática. vol. 33. Saltador. págs. 134–183. doi : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6. SEÑOR  0403962.