Complejidad temporal

En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo. La complejidad temporal se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo difieren en un factor constante como máximo.

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 del peor caso, que es la cantidad máxima de tiempo requerida para las entradas de un tamaño determinado. Menos común, y usualmente especificado explícitamente, es la complejidad del caso promedio, que es el promedio del tiempo necesario para las 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] Dado que esta función es generalmente difícil de calcular exactamente, y el tiempo de ejecución para entradas pequeñas generalmente no es consecuente, uno comúnmente se enfoca en el comportamiento de la complejidad cuando aumenta el tamaño de entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando 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 de entrada en unidades de bits necesarios 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 de tiempo $O(n^{\alpha })$ por alguna constante $\alpha >1$ es un algoritmo de tiempo polinómico .

Tabla de complejidades temporales comunes

La siguiente tabla resume algunas clases de complejidades de tiempo comúnmente encontradas. En la tabla, poly(x) = x^O(1), es decir, polinomial en x .

Nombre	Clase de complejidad	Tiempo de ejecución (T(n))	Ejemplos de tiempo de ejecución	Algoritmos de ejemplo
Tiempo constante		O(1)	10	Encontrar la mediana en un array ordenado de números.
Tiempo inverso de la función de Ackermann		O(α(n))		Tiempo amortizado por operación usando un conjunto disjunto
Tiempo de logaritmo iterado		O(logn*)		Coloración distribuida de grafos
Log-logaritmico		O(log log n)		Tiempo amortizado por operación usando una cola de prioridades^[2] acotada.
Tiempo logarítimico	DLOGTIME	O(log n)	log n, log(n²)	Búsqueda binaria
Tiempo polilogarítmico		poly(log n)	(log n)²
Poder fraccional		$O (n c)$ donde $0 < c < 1$	n^1/2, n^2/3	Buscando en un árbol kd
Tiempo lineal		O(n)	n, 2n + 5	Encontrar el item más grande o más pequeño en un array desordenado. Kadane's algorithm
Tiempo "n log-estrella n"		O(n log* n)		Algoritmo de triangulación de polígonos de Seidel
Tiempo linealitmico		O(n log n)	n log n, log n!	El ordenamiento por comparación más rápido posible; Transformada rápida de Fourier
Tiempo cuasilineal		n poly(log n)
Tiempo cuadrático		O(n²)	n²	Bubble sort; Insertion sort; Convolución directa
Tiempo cúbico		O(n³)	n³	Multiplicación ingenua de dos matrices de n×n. Cálculo decorrelación parcial.
Tiempo polinómico	P	2^O(log n) = poly(n)	n² + n, n¹⁰	Algoritmo de Karmarkar para programación lineal; Test de primalidad AKS^[3]^[4]
Tiempo cuasipolinomial	QP	2^poly(log n)	n^log log n, n^log n	O(log² n), mejoralgoritmo conocido de aproximación para el el problema del árbol de Steiner directo
Tiempo sub-exponencial (primera definición)	SUBEXP	O(2^{n^ε}) para todo ε > 0	O(2^{log n^{log log n}})
Tiempo sub-exponencial (segunda definición)		2^o(n)	2^{n^1/3}	Mejor algoritmo conocido para for factorización de enteros; anteriormente el mejor algoritmo para el problema del isomorfismo de grafos
Tiempo exponencial (con exponente lineal)	E	2^O(n)	1.1ⁿ, 10ⁿ	Resolución del problema del viajante usando programación dinámica
Tiempo exponencial	EXPTIME	2^poly(n)	2ⁿ, 2^n²	Resolución de multiplicación de matrices encadenadas via brute-force search
Tiempo factorial		O(n!)	n!	Resolviendo el problema del viajero usando búsqueda de fuerza bruta
Tiempo exponencial doble	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	Deciding the truth of a given statement in Aritmética de Presburguer

Tiempo constante

Se dice que un algoritmo es tiempo constante (también escrito como tiempo O(1)) si el valor de T(n) está limitado por un valor que no depende del tamaño de la entrada. Por ejemplo, acceder a cualquier elemento individual en una matriz requiere 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 también es una operación de tiempo constante ya que el resultado es siempre 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 lo tanto, este caso es una operación de tiempo lineal, que toma tiempo O(n). 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.

A pesar del nombre "tiempo constante", el tiempo de ejecución no tiene que ser independiente del tamaño del problema, pero un límite superior para el tiempo de ejecución tiene que estar limitado independientemente del tamaño del problema. Por ejemplo, la tarea "intercambia los valores de a y b si es necesario para que a ≤ b " se llama de tiempo constante aunque el tiempo pueda depender de si ya es cierto o no que a ≤ b . Sin embargo, hay una constante t tal que el tiempo requerido es siempre como máximo t .

Estos son algunos ejemplos de fragmentos de código que se ejecutan en tiempo constante. :

int index = 5;
int item = lista[index];
if (condición verdadera) then
  realizar alguna operación que se ejecuta en tiempo constante
else
  realizar alguna otra operación que se ejecute en tiempo constante
for i=1 to 100
  for j=1 to 200
   realizar alguna operación que se ejecuta en tiempo constante

Si T(n) es O(cualquier valor constante) se indica en notación estándar como T(n) siendo O(1).

Tiempo logarítmico

Se dice que un algoritmo toma tiempo logarítmico cuando T(n) = O(log n) . Dado que log _a n y log _b n están relacionados por un multiplicador constante, y dicho multiplicador es irrelevante para la clasificación big-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 toman tiempo logarítmico se encuentran comúnmente en operaciones con árboles binarios o cuando se usa la búsqueda binaria.

Un algoritmo O(log n) 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 aumenta n. Un algoritmo que debe acceder a todos los elementos de su entrada no puede tomar tiempo logarítmico ya que el tiempo necesario para leer una entrada de tamaño n es del orden de n .

Un ejemplo de tiempo logarítmico es la búsqueda dentro de un diccionario. Considere un diccionario $D$ que contiene n entradas, ordenadas por orden alfabético. Suponemos que, para $1 \leq k \leq n$ , uno puede acceder a la entrada $k$ del diccionario en un tiempo constante. Usemos $D (k)$ para denotar la $k$ -ésima entrada. Bajo estas hipótesis, la prueba de si una palabra $w$ está en el diccionario se puede hacer en tiempo logarítmico: considere $D(\lfloor n/2\rfloor ),$ dónde $\lfloor \;\rfloor$ denota la función de piso . Si $w=D(\lfloor n/2\rfloor ),$ entonces hemos terminado. Si no $w<D(\lfloor n/2\rfloor ),$ continuamos la búsqueda de la misma manera en la mitad izquierda del diccionario, de lo contrario continuamos de manera similar con la mitad derecha del diccionario. Este algoritmo es similar al método utilizado a menudo para encontrar una entrada en un diccionario de papel.

Tiempo poli-logarítmico

Se dice que un algoritmo se ejecuta en tiempo poli-logarítmico si T(n) = O ((log n )^k ), para alguna constante k. Por ejemplo, el orden de una matriz de cadena se puede resolver en tiempo poli-logarítmico en una máquina paralela de acceso aleatorio.^[5]

Tiempo sub-lineal

Se dice que un algoritmo se ejecuta en tiempo sub-lineal si T(n)=o(n). En particular, esto incluye algoritmos con las complejidades de tiempo definidas anteriormente.

Los algoritmos típicos que son exactos y, sin embargo, se ejecutan en tiempo sub-lineal usan el procesamiento paralelo (como lo hace el cálculo del determinante de una matriz NC₁), o alternativamente tienen suposiciones garantizadas en la estructura de entrada (como lo hacen la búsqueda binaria de tiempo logarítmico y muchos algoritmos de mantenimiento de árboles). Sin embargo, los lenguajes formales, como el conjunto de todas las cadenas que tienen un bit en la posición indicada por los primeros log (n) bits de la cadena pueden depender de cada bit de la entrada y, sin embargo, ser computables en tiempo sub-lineal.

El término específico algoritmo de tiempo sublineal generalmente se reserva a algoritmos que son diferentes a los anteriores en el sentido de que se ejecutan sobre modelos de máquinas seriales clásicas y donde no se permiten suposiciones previas en la entrada.^[6] Sin embargo, se les permite ser aleatorizados, y de hecho deben ser aleatorizados para todas las tareas excepto las más triviales.

Como tal, un algoritmo debe proporcionar una respuesta sin leer toda la entrada, sus detalles dependen en gran medida del acceso permitido a la entrada. Por lo general, para una entrada que se representa como una cadena binaria b₁,..., b_k se supone que el algoritmo puede solicitar y obtener el valor de b_i para cualquier i en tiempo O(1).

Los algoritmos de tiempo sub-lineal suelen ser aleatorios y solo proporcionan soluciones aproximadas. De hecho, la propiedad de una cadena binaria que solo tiene ceros puede demostrarse fácilmente que no puede ser decidida por un algoritmo de tiempo sub-lineal (no aproximado). Los algoritmos de tiempo sub-lineales surgen naturalmente en la investigación de property testing .

Tiempo lineal

Se dice que un algoritmo toma tiempo lineal, o tiempo $O (n)$ , si su complejidad temporal es $O (n)$ . 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 hay una constante $c$ tal que el tiempo de ejecución es 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 adición es constante o, al menos, está limitado por una constante.

El tiempo lineal es la mejor complejidad de tiempo posible en situaciones en las que un algoritmo tiene que leer secuencialmente toda su entrada. Por lo tanto, se ha invertido mucha investigación en descubrir algoritmos que exhiben tiempo lineal o, al menos, tiempo casi lineal. Esta investigación incluye métodos de software y hardware. Hay 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 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 T (n)=O(n log ^k n) para alguna constante positiva k;^[7] el caso de k=1 se llama tiempo linealitmico.^[8] Usando la notación O suave, estos algoritmos son Õ(n). Los algoritmos de tiempo cuasilineal también son O(n^1+ε) para cada constante ε> 0, y por lo tanto se ejecutan más rápido que cualquier algoritmo de tiempo polinómico cuyo límite de tiempo incluye un término n^c para cualquier c>1)

Los algoritmos que se ejecutan en tiempo cuasilineal incluyen:

Merge sort in-place, O(n log² n)
Quicksort, O(n log n), en su versión aleatoria, tiene un tiempo de ejecución que es O(n log n) en espera de la entrada del peor de los casos. Su versión no aleatoria tiene un tiempo de ejecución O(n log n) solo cuando se considera la complejidad promedio de los casos.
Heapsort, O(n log n), merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. en el peor de los casos
Transformadas rápidas de Fourier, O (n log n)
Cálculo de matriz Monge, O (n log n)

En muchos casos, el tiempo de ejecución n log n es simplemente el resultado de realizar una operación Θ (log n) n veces. Por ejemplo, el ordenamiento de un árboles binario crea un árbol binario insertando uno por uno los elementos de la matriz de tamaño n. Dado que la operación de inserción en un árbol de búsqueda binaria auto-balanceado toma tiempo O(log n ), todo el algoritmo toma tiempo O (n log n).

El ordenamiento por comparación requiere al menos Ω(n log n) comparaciones en el peor de los casos porque log (n!) = Θ(n log n), por aproximación de Stirling. Esto tiempos también surgen con frecuencia de la relación de recurrencia T(n) = 2T(n/2) + O (n).

Tiempo sub-cuadrático

Se dice que un algoritmo es de tiempo subcuadrático si T (n) = O(n²).

Por ejemplo, los algoritmos de ordenamiento simples basados en la comparación son cuadráticos (por ejemplo, ordenamiento por inserción) pero se pueden encontrar algoritmos más avanzados que son subcuadráticos (por ejemplo, ordenamiento shell). Ningún algoritmo de ordenamiento de propósito general se ejecuta en tiempo lineal pero la reducción de un tiempo cuadrático a uno 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 por una expresión polinómica en el tamaño de la entrada para el algoritmo, es decir, T (n) = O(n^k) para alguna constante positiva k.^[1]^[9] Los problemas para los que existe un algoritmo de tiempo polinómico 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 establece que el tiempo polinomial es sinónimo de "manejable", "factible", "eficiente" o "rápido".^[10]

Algunos ejemplos de algoritmos de tiempo polinomiales:

El ordenamiento por selección, para n enteros realiza $An^{2}$ operaciones para alguna constante A. Por lo tanto, corre en el tiempo $O(n^{2})$ y es un algoritmo de tiempo polinómico.
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 los grafos se pueden encontrar en el tiempo polinómico.

Tiempo polinomial fuerte y débil

En algunos contextos, especialmente en la optimización, uno diferencia entre el tiempo fuertemente polinomial y los algoritmos de tiempo débilmente polinomial . Estos dos conceptos solo son relevantes si las entradas a los algoritmos consisten en enteros.

El tiempo fuertemente polinómico se define en el modelo aritmético de computación. En este modelo de computación, las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) toman un paso de unidad de tiempo para realizar, independientemente de los tamaños de los operandos. El algoritmo se ejecuta en tiempo fuertemente polinómico si:^[11]

El número de operaciones en el modelo aritmético de computación está limitado por un polinomio en el número de enteros en la instancia de entrada; y
El espacio utilizado por el algoritmo está limitado por un polinomio en el tamaño de la entrada.

Cualquier algoritmo con estas dos propiedades se puede convertir en un algoritmo de tiempo polinómico reemplazando las operaciones aritméticas por algoritmos adecuados para realizar las operaciones aritméticas en una máquina de Turing . Si el segundo de los requisitos anteriores no se cumple, entonces esto ya no es cierto. Dado el entero $2^{n}$ (que ocupa un espacio proporcional a n en el modelo de máquina de Turing), es posible calcular $2^{2^{n}}$ con n multiplicaciones usando exponenciación binaria. Sin embargo, el espacio utilizado para representar $2^{2^{n}}$ es proporcional a $2^{n}$ y, por lo tanto, exponencial en lugar de polinomico en el espacio utilizado para representar la entrada. Por lo tanto, no es posible llevar a cabo este cálculo en tiempo polinómico en una máquina de Turing pero es posible calcularlo polinómicamente con muchas operaciones aritméticas.

Por el contrario, existen algoritmos que se ejecutan en varios pasos de la máquina de Turing delimitados por un polinomio en la longitud de la entrada codificada en binario pero no toman una serie de operaciones aritméticas delimitadas por un polinomio en el número de números de entrada. El algoritmo euclidiano para calcular el máximo divisor común de dos enteros es un ejemplo. Dados dos enteros $a$ y $b$ , el algoritmo realiza $O(\log \ a+\log \ b)$ operaciones aritméticas en números con como máximo $O(\log \ a+\log \ b)$ bits. Al mismo tiempo, el número de operaciones aritméticas no puede estar limitado por el número de enteros en la entrada (que es constante en este caso, siempre hay solo dos enteros en la entrada). Debido a la última observación, el algoritmo no se ejecuta en un tiempo fuertemente polinómico. Su tiempo real de ejecución depende de las magnitudes de $a$ y $b$ y no solo en el número de enteros en la entrada.

Se dice que un algoritmo que se ejecuta en tiempo polinomial pero que no es fuertemente polinomial se ejecuta en tiempo polinomial débil.^[12] Un ejemplo bien conocido de un problema para el que se conoce un algoritmo de tiempo polinomial débil, pero no se sabe que admita un algoritmo de tiempo polinomial fuerte, es la programación lineal. El tiempo débilmente polinomial no debe confundirse con el tiempo pseudopolinómico.

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 usando 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 polinómico
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 polinómico
ZPP	La clase de complejidad de los problemas de decisión que se pueden resolver con cero errores en una máquina de Turing probabilística en tiempo polinómico
RP	La clase de complejidad de los problemas de decisión que se pueden resolver con un error unilateral en una máquina de Turing probabilística en tiempo polinómico.
BPP	La clase de complejidad de los problemas de decisión que se pueden resolver con un error de 2 lados en una máquina de Turing probabilística en tiempo polinómico
BQP	La clase de complejidad de los problemas de decisión que se pueden resolver con un error de 2 lados en una máquina cuántica de Turing en tiempo polinómico

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 máquina. (Por ejemplo, un cambio de una máquina de Turing de una sola cinta a una máquina de varias cintas puede conducir a una aceleración cuadrática pero cualquier algoritmo que se ejecute en tiempo polinómico en un modelo también lo hace en el otro). Cualquier máquina abstracta tendrá una clase de complejidad correspondiente a los problemas que se pueden resolver en tiempo polinómico en esa máquina.

Tiempo superpolinomial

Se dice que un algoritmo toma tiempo superpolinomial si T (n) no está limitado por ningún polinomio. Usando una notación omega chica, es el 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 tiempo superpolinomial (más específicamente, tiempo exponencial).

Un algoritmo que utiliza recursos exponenciales es claramente superpolinomial, pero algunos algoritmos son muy débilmente superpolinomiales. Por ejemplo, la prueba de primalidad Adleman – Pomerance – Rumely se ejecuta durante n^{O(log log n)} en entradas de n bits; esto crece más rápido que cualquier polinomio para una n lo suficientemente grande pero el tamaño de entrada debe hacerse tan grande como para volverse impráctico si se quiere evitar ser dominado por un polinomio de pequeño grado.

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. Dado que el problema P versus NP no está resuelto, actualmente no se sabe de un algoritmo para un problema NP completo que se ejecute en tiempo polinómico.

Tiempo cuasi polinomial

Los algoritmos de tiempo cuasi polinomiales son algoritmos que funcionan más lentamente que aquellos de tiempo polinómico pero no tan lentos como para ser de tiempo exponencial. El peor tiempo de ejecución de un algoritmo de tiempo cuasi polinomial es $2^{O((\log n)^{c})}$ para una constante $c>0$ . Para $c=1$ obtenemos un algoritmo de tiempo polinómico, para $c<1$ obtenemos un algoritmo de tiempo sub-lineal.

Los algoritmos de tiempo cuasi polinomiales generalmente surgen en reducciones de un problema NP-hard a otro problema. Por ejemplo, uno puede tomar una instancia de un problema NP-hard, digamos 3SAT, y convertirlo en una instancia de otro problema B, pero el tamaño de la instancia se convierte en $2^{O((\log n)^{c})}$ . En ese caso, esta reducción no prueba que el problema B sea NP-hard; esta reducción solo muestra que no existe un algoritmo de tiempo polinómico para B a menos que exista un algoritmo de tiempo cuasi polinómico para 3SAT (y, por lo tanto, todo NP). De manera similar, existen algunos problemas para los cuales conocemos algoritmos de tiempo cuasi-polinomiales pero no de tiempo polinomial. Tales problemas surgen en los algoritmos de aproximación; Un ejemplo famoso es el problema del árbol Steiner dirigido, para el cual existe un algoritmo de aproximación de tiempo cuasi polinomial que logra un factor de aproximación de $O(\log ^{3}n)$ (n es el número de vértices), pero la demostración de la existencia de dicho algoritmo de tiempo polinomial es un problema abierto.

Otros problemas computacionales con soluciones de tiempo cuasi-polinomiales pero ninguna solución de tiempo polinomial conocida incluye el problema de planted cliques en el que el objetivo es encontrar un clique mayor en la unión de una clique y un grafo aleatorio. Aunque cuasi-polinomialmente solucionable, se ha conjeturado que el problema de planted cliques no tiene una solución de tiempo polinomial; Esta conjetura se ha utilizado como un supuesto de dureza computacional para demostrar la dificultad de varios otros problemas en la teoría de juegos computacionales, property testing y el aprendizaje automático.^[13]

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

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

Relación con problemas NP-completos

En teoría de la complejidad, el problema de P versus NP sin resolver 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 tiempo exponencial. De hecho, se conjetura para muchos problemas naturales completos de NP que no tienen algoritmos de tiempo sub-exponenciales. Aquí "tiempo sub-exponencial" se entiende como la segunda definición presentada 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.^[15] Dado que se conjetura que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales, algunos resultados de inaplicabilidad en el campo de los algoritmos de aproximación suponen que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales. Por ejemplo, vea los resultados de inaplicabilidad conocidos para el problema de la cobertura de conjuntos.

Tiempo sub-exponencial

El término tiempo sub-exponencial se usa para expresar que el tiempo de ejecución de algún algoritmo puede crecer más rápido que cualquier polinomio pero aún es significativamente más pequeño que un exponencial. En este sentido, los problemas que tienen algoritmos de tiempo sub-exponenciales son algo más manejables que aquellos que solo tienen algoritmos exponenciales. Generalmente no hay consenso respecto a la definición precisa de "sub-exponencial",^[16] enumeramos las dos más utilizados a continuación:

Primera definición

Se dice que un problema puede resolverse con un tiempo sub-exponencial si se puede resolver en tiempos de ejecución cuyos logaritmos crecen más lentamente que cualquier polinomio dado. Más precisamente, un problema toma un tiempo sub-exponencial si por 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:^[17]^[18]^[19]^[20]

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

Esta noción de sub-exponencial 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 sub-exponencial como tiempos de ejecución en 2^o(n).^[15]^[21]^[22] Esta definición permite tiempos de ejecución mayores que la primera definición de tiempo sub-exponencial. Un ejemplo de dicho algoritmo de tiempo sub-exponencial es el algoritmo clásico más conocido para la factorización de enteros, la criba general del cuerpo de números , que se ejecuta en un tiempo de $2^{{\tilde {O}}(n^{1/3})}$ , donde n es la longitud de la entrada. Otro ejemplo es el problema del isomorfismo de grafos, donde el algoritmo de Luks se ejecuta a tiempo $2^{O({\sqrt {n\log n}})}$ . (En 2015–2017, Babai redujo la complejidad de este problema al tiempo cuasi polinomial.)

Si el algoritmo puede ser sub-exponencial en el tamaño de la instancia, el número de vértices o el número de aristas, eso hace una diferencia. En la complejidad parametrizada, esta diferencia se hace explícita considerando 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 sub-exponencial en k y en tiempo polinomico en el tamaño de entrada n:^[23]

{\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 $(L,k)$ para los cuáles hay una función computable $f:\mathbb {N} \to \mathbb {N}$ con $f\in o(k)$ y un algoritmo que decide L en tiempo $2^{f(k)}\cdot {\text{poly}}(n)$ .

Hipótesis de tiempo exponencial

La hipótesis del tiempo exponencial (ETH ) es que 3SAT, el problema de satisfacción de las fórmulas booleanas en forma conjuntiva normal con, como máximo, tres literales por cláusula y con n variables, no puede resolverse en el tiempo 2^o(n) . Más precisamente, la hipótesis es que existe una constante absoluta $c >0$ tal que 3SAT no puede decidirse en tiempo 2^cn por ninguna máquina determinista de Turing. 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 entero $k \geq 3$ ^[24] 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 por 2^poly(n), donde poly(n) es un polinomio en n. Más formalmente, un algoritmo es de tiempo exponencial si T(n) está limitado 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.

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

A veces, el tiempo exponencial se usa 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.

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

Tiempo factorial

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 mezclando repetidamente la lista hasta que se encuentre ordenada. En el caso promedio, cada paso 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 pedidos. Bogosort comparte patrimonio con el teorema del mono infinito .

Doble tiempo exponencial

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

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

Los algoritmos de tiempo doble exponencial bien conocidos incluyen:

Procedimientos de decisión para la aritmética de Presburger
Computación de una base de Gröbner (en el peor de los casos^[25])
La eliminación del cuantificador en campos cerrados reales requiere al menos un tiempo exponencial doble^[26]^[27]

Referencias

↑ ^a ^b Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
↑ Mehlhorn, Kurt; Naher, Stefan (1990). «Bounded ordered dictionaries in O(log log N) time and O(n) space». Information Processing Letters 35 (4): 183-189. doi:10.1016/0020-0190(90)90022-P.
↑ Tao, Terence (2010). «1.11 The AKS primality test». An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics 117. Providence, RI: American Mathematical Society. pp. 82-86. ISBN 978-0-8218-5280-4. doi:10.1090/gsm/117.
↑ Lenstra, Jr., H.W.; Pomerance, Carl (11 de diciembre de 2016). Primality testing with Gaussian periods.
↑ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). «Efficient Matrix Chain Ordering in Polylog Time». SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 27 (2): 466-490. ISSN 1095-7111. doi:10.1137/S0097539794270698.
↑ Kumar, Ravi; Rubinfeld, Ronitt (2003). «Sublinear time algorithms». SIGACT News 34 (4): 57-67. doi:10.1145/954092.954103.
↑ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). «On Quasilinear Time Complexity Theory». Theoretical Computer Science 148 (2): 325-349. doi:10.1016/0304-3975(95)00031-q. Consultado el 23 de febrero de 2015.
↑ Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed. p. 186. Pearson Education, Inc.
↑ Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
↑ Cobham, Alan (1965). «The intrinsic computational difficulty of functions». Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
↑ Grötschel, Martin; László Lovász; Alexander Schrijver (1988). «Complexity, Oracles, and Numerical Computation». Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.
↑ Schrijver, Alexander (2003). «Preliminaries on algorithms and Complexity». Combinatorial Optimization: Polyhedra and Efficiency 1. Springer. ISBN 3-540-44389-4.
↑ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest- $k$ -subgraph with perfect completeness, Bibcode:2015arXiv150408352B ..
↑ Complexity Zoo: Class QP: Quasipolynomial-Time
↑ ^a ^b Impagliazzo, R.; Paturi, R. (2001). «On the complexity of k-SAT». Journal of Computer and System Sciences (Elsevier) 62 (2): 367-375. ISSN 1090-2724. doi:10.1006/jcss.2000.1727.
↑ Aaronson, Scott (5 de abril de 2009). «A not-quite-exponential dilemma». Shtetl-Optimized. Consultado el 2 de diciembre de 2009.
↑ Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). «BPP has subexponential time simulations unless EXPTIME has publishable proofs». Computational Complexity (Berlin, New York: Springer-Verlag) 3 (4): 307-318. doi:10.1007/BF01275486.
↑ Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time
↑ Philippe Moser (2003). Baire’s Categories on Small Complexity Classes 2751. pp. 333-342. ISBN 978-3-540-40543-6. doi:10.1007/978-3-540-45077-1_31.
↑ Miltersen, P.B. (2001). «Derandomizing Complexity Classes». Handbook of Randomized Computing. Combinatorial Optimization (Kluwer Academic Pub) 9: 843. ISBN 978-1-4613-4886-3. doi:10.1007/978-1-4615-0013-1_19.
↑ Kuperberg, Greg (2005). «A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem». SIAM Journal on Computing (Philadelphia) 35 (1): 188. ISSN 1095-7111. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345.
↑ «A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space». arXiv:quant-ph/0406151v1. 2004.
↑ Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. p. 417. ISBN 978-3-540-29952-3. Archivado desde el original el 18 de noviembre de 2007. Consultado el 14 de julio de 2020.
↑ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). «Which problems have strongly exponential complexity?». Journal of Computer and System Sciences 63 (4): 512-530. doi:10.1006/jcss.2001.1774.
↑ Mayr,E. & Mayer,A.: The Complexity of the Word Problem for Commutative Semi-groups and Polynomial Ideals. Adv. in Math. 46(1982) pp. 305–329
↑ J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential. J. Symbolic Comp. 5(1988) pp. 29–35.
↑ G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture Notes in Computer Science 33) pp. 134–183

Datos: Q2393193

[Sipser-1] Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.

[2] Mehlhorn, Kurt; Naher, Stefan (1990). «Bounded ordered dictionaries in O(log log N) time and O(n) space». Information Processing Letters 35 (4): 183-189. doi:10.1016/0020-0190(90)90022-P.

[tao-aks-3] Tao, Terence (2010). «1.11 The AKS primality test». An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics 117. Providence, RI: American Mathematical Society. pp. 82-86. ISBN 978-0-8218-5280-4. doi:10.1090/gsm/117.

[4] Lenstra, Jr., H.W.; Pomerance, Carl (11 de diciembre de 2016). Primality testing with Gaussian periods.

[5] Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). «Efficient Matrix Chain Ordering in Polylog Time». SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 27 (2): 466-490. ISSN 1095-7111. doi:10.1137/S0097539794270698.

[6] Kumar, Ravi; Rubinfeld, Ronitt (2003). «Sublinear time algorithms». SIGACT News 34 (4): 57-67. doi:10.1145/954092.954103.

[7] Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). «On Quasilinear Time Complexity Theory». Theoretical Computer Science 148 (2): 325-349. doi:10.1016/0304-3975(95)00031-q. Consultado el 23 de febrero de 2015.

[8] Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed. p. 186. Pearson Education, Inc.

[9] Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.

[10] Cobham, Alan (1965). «The intrinsic computational difficulty of functions». Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[11] Grötschel, Martin; László Lovász; Alexander Schrijver (1988). «Complexity, Oracles, and Numerical Computation». Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

[12] Schrijver, Alexander (2003). «Preliminaries on algorithms and Complexity». Combinatorial Optimization: Polyhedra and Efficiency 1. Springer. ISBN 3-540-44389-4.

[13] Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest- $k$ -subgraph with perfect completeness, Bibcode:2015arXiv150408352B ..

[14] Complexity Zoo: Class QP: Quasipolynomial-Time

[ETH-15] Impagliazzo, R.; Paturi, R. (2001). «On the complexity of k-SAT». Journal of Computer and System Sciences (Elsevier) 62 (2): 367-375. ISSN 1090-2724. doi:10.1006/jcss.2000.1727.

[16] Aaronson, Scott (5 de abril de 2009). «A not-quite-exponential dilemma». Shtetl-Optimized. Consultado el 2 de diciembre de 2009.

[bpp-17] Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). «BPP has subexponential time simulations unless EXPTIME has publishable proofs». Computational Complexity (Berlin, New York: Springer-Verlag) 3 (4): 307-318. doi:10.1007/BF01275486.

[18] Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time

[19] Philippe Moser (2003). Baire’s Categories on Small Complexity Classes 2751. pp. 333-342. ISBN 978-3-540-40543-6. doi:10.1007/978-3-540-45077-1_31.

[20] Miltersen, P.B. (2001). «Derandomizing Complexity Classes». Handbook of Randomized Computing. Combinatorial Optimization (Kluwer Academic Pub) 9: 843. ISBN 978-1-4613-4886-3. doi:10.1007/978-1-4615-0013-1_19.

[21] Kuperberg, Greg (2005). «A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem». SIAM Journal on Computing (Philadelphia) 35 (1): 188. ISSN 1095-7111. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345.

[22] «A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space». arXiv:quant-ph/0406151v1. 2004.

[23] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. p. 417. ISBN 978-3-540-29952-3. Archivado desde el original el 18 de noviembre de 2007. Consultado el 14 de julio de 2020.

[24] Impagliazzo, R.; Paturi, R.; Zane, F. (2001). «Which problems have strongly exponential complexity?». Journal of Computer and System Sciences 63 (4): 512-530. doi:10.1006/jcss.2001.1774.

[25] Mayr,E. & Mayer,A.: The Complexity of the Word Problem for Commutative Semi-groups and Polynomial Ideals. Adv. in Math. 46(1982) pp. 305–329

[26] J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential. J. Symbolic Comp. 5(1988) pp. 29–35.

[27] G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture Notes in Computer Science 33) pp. 134–183

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]