Complejidad del tiempo

Estimación del tiempo necesario para ejecutar un algoritmo

"Tiempo de ejecución" vuelve a dirigir aquí. Para ver la película, vea Running Time (película) .

Gráficos de funciones comúnmente utilizadas en el análisis de algoritmos , que muestran el número de operaciones N frente al tamaño de entrada n para cada función.

En ciencias de la computación , la complejidad del tiempo es la complejidad computacional que describe la cantidad de tiempo que lleva la computadora 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 fija de tiempo para realizarse. Por lo tanto, la cantidad de tiempo que toma y el número de operaciones elementales realizadas por el algoritmo difieren como máximo en 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 de tiempo del peor de los casos , que es la cantidad máxima de tiempo requerida para entradas de un tamaño dado. Menos común, y por lo general se especifica explícitamente, es la complejidad de caso promedio , que es el promedio del tiempo empleado en entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de entradas posibles de un tamaño dado). En ambos casos, la complejidad del tiempo se expresa generalmente en función del tamaño de la entrada. ^{[1] : 226}Dado que esta función es generalmente difícil de calcular con exactitud 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 la entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad de tiempo se expresa comúnmente usando gran notación O , típicamente , , , , etc., donde n es el tamaño de entrada en unidades de bits de 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 de tiempo es un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo para alguna constante es un algoritmo de tiempo polinomial .${\displaystyle O(n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle \alpha >1}$

Tabla de complejidades temporales comunes

Más información: Complejidad computacional de operaciones matemáticas

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

Nombre	Clase de complejidad	Tiempo de ejecución ( T ( n ))	Ejemplos de tiempos de ejecución	Algoritmos de ejemplo
tiempo constante		O (1)	10	Encontrar el valor mediano en una matriz ordenada de números Calculando (−1) n
tiempo inverso de Ackermann		O ( α ( n ))		Tiempo amortizado por operación usando un conjunto disjunto
tiempo logarítmico iterado		O ( registro *  n )		Coloración distribuida de ciclos
log-logarítmico		O (log log n )		Tiempo amortizado por operación usando una cola de prioridad limitada [2]
tiempo logarítmico	DLOGTIME	O (log  n )	log  n , log ( n 2 )	Búsqueda binaria
tiempo polilogarítmico		poli (log  n )	(log  n ) 2
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 , 2 n + 5	Encontrar el elemento más pequeño o más grande en una matriz sin clasificar , el algoritmo de Kadane , búsqueda lineal
"n log-star n" tiempo		O ( n log * n )		Seidel 's polígono triangulación algoritmo.
tiempo linealitmico		O ( n log n )	n log n , log n !	Clasificación de comparación más rápida posible ; Transformada rápida de Fourier .
tiempo cuasilineal		n poli (log n )
tiempo cuadrático		O ( n 2 )	n 2	Tipo de burbuja ; Tipo de inserción ; Convolución directa
tiempo cúbico		O ( n 3 )	n 3	Multiplicación ingenua de dos matrices n × n . Cálculo de correlación parcial .
tiempo polinomial	PAG	2 O (log n ) = poli ( n )	n 2 + n , n 10	Algoritmo de Karmarkar para programación lineal ; Prueba de originalidad de AKS [3] [4]
tiempo cuasi-polinomial	QP	2 poli (log  n )	n log log n , n log  n	O (log 2 n ) más conocido : algoritmo de aproximación para el problema del árbol de Steiner dirigido .
tiempo sub-exponencial (primera definición)	SUBEXP	O (2 n ε ) para todo ε > 0		Contiene BPP a menos que EXPTIME (ver más abajo) sea igual a MA . [5]
tiempo sub-exponencial (segunda definición)		2 o ( n )	2 n 1/3	El algoritmo más conocido para la factorización de enteros ; anteriormente el mejor algoritmo para isomorfismo de grafos
tiempo exponencial (con exponente lineal)	mi	2 O ( n )	1,1 n , 10 n	Resolviendo el problema del viajante de comercio usando programación dinámica
tiempo exponencial	EXPTIME	2 poli ( n )	2 n , 2 n 2	Resolver la multiplicación de cadenas de matrices mediante la búsqueda de fuerza bruta
tiempo factorial		Oh ( n !)	n !	Resolviendo el problema del viajante a través de la búsqueda por fuerza bruta
doble tiempo exponencial	2-EXPTIME	2 2 poli ( n )	2 2 n	Decidir la verdad de una declaración dada en aritmética de Presburger

Tiempo constante

El "tiempo constante" vuelve a dirigir aquí. Para conocer la técnica de programación para evitar un ataque de sincronización, consulte Ataque de sincronización § Evitación .

Se dice que un algoritmo es tiempo constante (también escrito como O (1) tiempo) 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 lleva un tiempo constante ya que solo se debe realizar una operación para ubicarlo. 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, tomando O( n ) tiempo. Sin embargo, si el número de elementos se conoce de antemano y no cambia, 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 acotado independientemente del tamaño del problema. Por ejemplo, la tarea "intercambio de los valores de una y b si es así necesario que un ≤ b " se denomina constante de tiempo aunque el tiempo puede depender de si o no lo que ya es cierto que un ≤ b . Sin embargo, existe una constante t tal que el tiempo requerido es siempre como máximo t .

A continuación, se muestran algunos ejemplos de fragmentos de código que se ejecutan en tiempo constante:

int índice = 5;
int elemento = lista [índice];si (condición verdadera) entonces realizar alguna operación que se ejecuta en tiempo constantedemás realizar alguna otra operación que se ejecute en tiempo constantepara i = 1 a 100 para j = 1 a 200 realizar alguna operación que se ejecuta en tiempo constante

Si T ( n ) es O ( cualquier valor constante ), esto es equivalente ay se expresa en notación estándar como T ( n ) es O (1).

Tiempo logarítmico

Más información: Crecimiento logarítmico

Se dice que un algoritmo toma el 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 de O grande, el uso estándar para los 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 el tiempo logarítmico se encuentran comúnmente en operaciones en á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 n aumenta. 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 lo da la búsqueda en el diccionario. Considere un diccionario D que contiene n entradas, ordenadas por orden alfabético . Suponemos que, para 1 ≤ k ≤ n , se puede acceder a la k- ésima entrada del diccionario en un tiempo constante. Sea D ( k ) 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 , entonces hemos terminado. De lo contrario, si${\displaystyle D(\lfloor n/2\rfloor )}$${\displaystyle \lfloor \;\rfloor }$${\displaystyle w=D(\lfloor n/2\rfloor )}$${\displaystyle w<D(\lfloor n/2\rfloor )}$, continúe la búsqueda de la misma manera en la mitad izquierda del diccionario, de lo contrario continúe 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 en papel.

Tiempo polilogarítmico

Se dice que un algoritmo se ejecuta en tiempo polilogarítmico si su tiempo T ( n ) es O ((log n ) ^k ) para alguna constante k . Otra forma de escribir esto es O (log ^k n ) .

Por ejemplo, el orden de la cadena matricial se puede resolver en tiempo polilogarítmico en una máquina de acceso aleatorio en paralelo , ^[6] y se puede determinar que un gráfico es plano de una manera completamente dinámica en tiempo O (log ³ n ) por operación de inserción / eliminación . ^[7]

Tiempo sub-lineal

Se dice que un algoritmo se ejecuta en tiempo sublineal (a menudo escrito como tiempo sublineal ) 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 aún se ejecutan en tiempo sub-lineal usan procesamiento paralelo (como lo hace el cálculo determinante de la matriz NC ₁ ), o alternativamente tienen supuestos garantizados 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 de 1 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 sublineal.

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

Como tal 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 en el tiempo O (1) solicitar y obtener el valor de b _i para cualquier i .

Los algoritmos de tiempo sub-lineal suelen ser aleatorios y solo proporcionan soluciones aproximadas . De hecho, se puede probar fácilmente que la propiedad de una cadena binaria que solo tiene ceros (y ninguno) no es decidible mediante un algoritmo de tiempo sublineal (no aproximado). Los algoritmos de tiempo sub-lineal surgen naturalmente en la investigación de las pruebas de propiedades .

Tiempo lineal

Se dice que un algoritmo toma tiempo lineal , u O ( n ) tiempo, si su complejidad de tiempo es O ( n ) . De manera informal, esto significa que el tiempo de ejecución aumenta como máximo linealmente con el tamaño de la entrada. Más precisamente, esto significa que hay una constante c 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 suma 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 el algoritmo tiene que leer secuencialmente toda su entrada. Por lo tanto, se ha invertido mucha investigación en el descubrimiento de algoritmos que exhiban un tiempo lineal o, al menos, un tiempo casi lineal. Esta investigación incluye métodos tanto de software como de hardware. Hay varias tecnologías de hardware que aprovechan 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 un tiempo cuasilineal (también denominado tiempo log-lineal ) si T ( n ) = O ( n log ^k n ) para alguna constante positiva k ; ^{[9] el} tiempo linealítmico es el caso k = 1 . ^[10] Utilizando 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 ejecuta más rápido que cualquier algoritmo de tiempo polinomial cuyo límite de tiempo incluye un término n ^c para cualquier c > 1 .

Los algoritmos que se ejecutan en tiempo cuasilineal incluyen:

• Orden de fusión en el lugar , O ( n log ² n )
• Quicksort , O ( n log n ), en su versión aleatorizada, tiene un tiempo de ejecución que es O ( n log n ) a la 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 ), combinación de ordenación , introsortización , ordenación de árbol binario, ordenación suave , ordenación de paciencia , etc. en el peor de los casos
• Transformadas rápidas de Fourier , O ( n log n )
• Cálculo de la matriz de 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 (para la notación, consulte la 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 de búsqueda binaria autoequilibrado toma O (log n ) tiempo, todo el algoritmo toma O ( n log n ) tiempo.

Los tipos de comparación requieren al menos comparaciones de Ω ( n log n ) en el peor de los casos porque log ( n !) = Θ ( n log n ) , según la aproximación de Stirling . También surgen con frecuencia de la relación de recurrencia T ( n ) = 2 T ( n / 2) + O ( n ) .

Tiempo subcuadrático

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

Por ejemplo, los algoritmos de clasificación simples basados ​​en comparación 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 ). Ningún ordenamiento 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 polinomial si su tiempo de ejecución está acotado 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] [11]} 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 . Tesis de Cobhamestablece que el tiempo polinomial es sinónimo de "manejable", "factible", "eficiente" o "rápido". ^[12]

Algunos ejemplos de algoritmos de tiempo polinomial:

• La ordenación por selección algoritmo de ordenación de n enteros Realiza operaciones para alguna 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 coincidencias máximas en los gráficos se pueden encontrar en tiempo polinomial.

Tiempo fuerte y débilmente polinomial

En algunos contextos, especialmente en la optimización , se 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 números enteros.

El tiempo fuertemente polinomial se define en el modelo aritmético de cálculo. En este modelo de cálculo, las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) requieren un paso de tiempo unitario para realizar, independientemente del tamaño de los operandos. El algoritmo se ejecuta en un tiempo fuertemente polinomial si: ^[13]

1. el número de operaciones en el modelo aritmético de cálculo está acotado por un polinomio en el número de enteros en la instancia de entrada; y
2. el espacio utilizado por el algoritmo está delimitado por un polinomio en el tamaño de la entrada.

Cualquier algoritmo con estas dos propiedades se puede convertir en un algoritmo de tiempo polinomial reemplazando las operaciones aritméticas por algoritmos adecuados para realizar las operaciones aritméticas en una máquina de Turing . Si no se cumple el segundo de los requisitos anteriores, esto ya no es así. Dado el número entero (que ocupa un espacio proporcional an en el modelo de la máquina de Turing), es posible calcular con n multiplicaciones usando el cuadrado repetido . Sin embargo, el espacio utilizado para representar es proporcional a${\displaystyle 2^{n}}$${\displaystyle 2^{2^{n}}}$${\displaystyle 2^{2^{n}}}$${\displaystyle 2^{n}}$, y por lo tanto exponencial en lugar de polinomio en el espacio utilizado para representar la entrada. Por lo tanto, no es posible realizar este cálculo en tiempo polinomial en una máquina de Turing, pero es posible calcularlo polinomialmente muchas operaciones aritméticas.

Por el contrario, hay algoritmos que se ejecutan en varios pasos de la máquina de Turing limitados por un polinomio en la longitud de la entrada codificada en binario, pero no toman una serie de operaciones aritméticas limitadas por un polinomio en el número de números de entrada. El algoritmo euclidiano para calcular el máximo común divisor de dos enteros es un ejemplo. Dados dos enteros y , el algoritmo realiza operaciones aritméticas en números con como máximo${\displaystyle a}$${\displaystyle b}$${\displaystyle O(\log a+\log b)}$${\displaystyle O(\log a+\log b)}$bits. Al mismo tiempo, el número de operaciones aritméticas no puede estar acotado 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 polinomial. Su tiempo de funcionamiento real, depende de las magnitudes de y no sólo en el número de enteros en la entrada.${\displaystyle a}$${\displaystyle b}$

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

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 tiempo polinomial son las siguientes.

PAG	La clase de complejidad de los problemas de decisión que se pueden resolver en una máquina de Turing determinista en tiempo polinomial.
notario público	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 se pueden resolver con cero error en una máquina de Turing probabilística en tiempo polinomial.
RP	La clase de complejidad de problemas de decisión que se pueden resolver con un error de un lado en una máquina de Turing probabilística en tiempo polinomial.
BPP	La clase de complejidad de los problemas de decisión que se pueden resolver 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 de dos caras en una máquina cuántica de Turing en tiempo polinomial

P es la clase de complejidad de tiempo más pequeña en una máquina determinista que es robusta en términos de cambios de modelo de máquina. (Por ejemplo, un cambio de una sola cinta de máquina de Turing a una máquina multi-cinta puede conducir a un aumento de velocidad de segundo grado, pero cualquier algoritmo que se ejecuta en tiempo polinómico bajo un mismo modelo también lo hace en la otra.) Cualquier determinada máquina abstracta voluntad tienen una clase de complejidad correspondiente a los problemas que se pueden resolver en tiempo polinomial en esa máquina.

Tiempo superpolinomial

Se dice que un algoritmo toma tiempo superpolinomial si T ( n ) no está acotado arriba por ningún polinomio. Usando poca notación omega , es ω ( n ^c ) tiempo 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 usa recursos exponenciales es claramente superpolinomial, pero algunos algoritmos son solo superpolinomiales muy débilmente. Por ejemplo, la prueba de primalidad 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 suficientemente grande , pero el tamaño de entrada debe volverse impracticablemente grande antes de que no pueda ser dominado por un polinomio con grado pequeño.

Un algoritmo que requiere mentiras tiempo superpolynomial 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 de 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 que se ejecutan más tiempo que el tiempo polinomial, pero no tanto como para ser tiempo exponencial. El peor tiempo de ejecución de un algoritmo de tiempo cuasi-polinómico es fijo . Pues obtenemos un algoritmo de tiempo polinomial, ya que obtenemos un algoritmo de tiempo sublineal.${\displaystyle 2^{O(\log ^{c}n)}}$${\displaystyle c>0}$${\displaystyle c=1}$${\displaystyle c<1}$

Los algoritmos de tiempo cuasi-polinomial surgen típicamente en reducciones de un problema NP-difícil a otro problema. Por ejemplo, se puede tomar una instancia de un problema NP difícil, digamos 3SAT , y convertirla en una instancia de otro problema B, pero el tamaño de la instancia pasa a ser . En ese caso, esta reducción no prueba que el problema B sea NP-difícil; esta reducción solo muestra que no hay un algoritmo de tiempo polinomial para B a menos que haya un algoritmo de tiempo cuasi-polinomial para 3SAT (y por lo tanto todo NP ). De manera similar, existen algunos problemas para los que conocemos algoritmos de tiempo cuasi-polinomial, pero no se conoce ningún algoritmo de tiempo polinomial. Tales problemas surgen en los algoritmos de aproximación; un ejemplo famoso es el dirigido${\displaystyle 2^{O(\log ^{c}n)}}$Problema del árbol de Steiner , 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 mostrar 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-polinomiales pero sin una 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 cuasi polinomialmente solucionable, se ha conjeturado que el problema de la camarilla plantada no tiene una solución de tiempo polinomial; Esta conjetura de camarilla plantada se ha utilizado como un supuesto de dureza computacional para probar la dificultad de varios otros problemas en la teoría de juegos computacionales , las pruebas de propiedades y el aprendizaje automático . ^[15]

La clase de complejidad QP consta de todos los problemas que tienen algoritmos de tiempo cuasi-polinomiales. Puede definirse 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, para muchos problemas NP-completos naturales se conjetura que no tienen algoritmos de tiempo sub-exponenciales. Aquí se considera que "tiempo subexponencial" significa la segunda definición que se presenta a continuación. (Por otro lado, muchos problemas de gráficos 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) es conocida como la hipótesis del tiempo exponencial . ^[17]Dado que se conjetura que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales, algunos resultados de inaproximación en el campo de los algoritmos de aproximación suponen que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales. Por ejemplo, consulte los resultados de inapropiabilidad conocidos para el problema de la cobertura del conjunto .

Tiempo sub-exponencial

El término sub-exponencial de tiempo se utiliza para expresar que el tiempo de funcionamiento de algún algoritmo puede crecer más rápido que cualquier polinomio, pero todavía es significativamente más pequeño que una exponencial. En este sentido, los problemas que tienen algoritmos de tiempo sub-exponenciales son algo más manejables que los que solo tienen algoritmos exponenciales. La definición precisa de "sub-exponencial" no está generalmente acordada, ^[18] y enumeramos las dos más utilizadas a continuación.

Primera definicion

Se dice que un problema se puede resolver en el tiempo sub-exponencial si se puede resolver en tiempos de ejecución cuyos logaritmos crecen más pequeños que cualquier polinomio dado. Más precisamente, un problema está en tiempo sub-exponencial 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 como sigue. ^{[5] [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 sub-exponencial como tiempos de ejecución en 2 ^{o ( n )} . ^{[17] [22] [23]} Esta definición permite tiempos de ejecución mayores que la primera definición de tiempo sub-exponencial. Un ejemplo de tal algoritmo de tiempo sub-exponencial 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 de grafos , que resolvió el algoritmo más conocido de 1982 a 2016 . Sin embargo, en STOC 2016 se presentó un algoritmo de tiempo cuasi-polinomial.${\displaystyle 2^{{\tilde {O}}(n^{1/3})}}$${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$^[24]

Hace una diferencia si se permite que el algoritmo sea sub-exponencial 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 el tiempo sub-exponencial en k y polinomio 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 con parámetros 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

Artículo principal: 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 3SAT no puede ser decidido 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 número entero k ≥ 3 . ^[26] La hipótesis del tiempo exponencial implica P ≠ NP .

Tiempo exponencial

Se dice que un algoritmo es tiempo exponencial , si T ( n ) está delimitado en la parte superior por 2 ^{poli ( n )} , donde poli ( n ) es algún polinomio en n . Más formalmente, un algoritmo es 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 {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 .

${\displaystyle {\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 barajando repetidamente la lista hasta que se encuentra que está ordenada. En el caso promedio, cada pasada a través del algoritmo bogosort examinará uno de los n ! pedidos 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 .

Doble tiempo exponencial

Se dice que un algoritmo es el tiempo exponencial doble si T ( n ) está delimitado en la parte superior 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 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 . ISBN de Course Technology Inc. 0-619-21764-2.
2. Mehlhorn, Kurt ; Naher, Stefan (1990). "Diccionarios ordenados delimitados 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" . Un épsilon de habitación, II: páginas del tercer año de un blog de matemáticas . Estudios de Posgrado en Matemáticas. 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 .; Pomerance, 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 . Señor 3941463 .  
5. Babai, László ; Fortnow, Lance ; Nisan, N .; Wigderson, Avi (1993). "BPP tiene simulaciones de tiempo subexponenciales a menos que EXPTIME tenga pruebas publicables". Complejidad computacional . Berlín, Nueva York: Springer-Verlag . 3 (4): 307–318. doi : 10.1007 / BF01275486 . S2CID 14802332 . 
6. Bradford, Phillip G .; Rawlins, Gregory JE; Shannon, Gregory E. (1998). "Orden de cadena de matriz eficiente en tiempo polylog". Revista SIAM de Computación . 27 (2): 466–490. doi : 10.1137 / S0097539794270698 . Señor 1616556 . 
7. Holm, Jacob; Rotenberg, Eva (2020). "Ensayo de planaridad totalmente dinámico 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 . Asociación para Maquinaria de Computación. págs. 167–180. arXiv : 1911.03449 . doi : 10.1145 / 3357713.3384249 .
8. Kumar, Ravi; Rubinfeld, Ronitt (2003). "Algoritmos de tiempo sublineal" (PDF) . Noticias SIGACT . 34 (4): 57–67. doi : 10.1145 / 954092.954103 . S2CID 65359 .  
9. 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 .  
10. Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4ª ed.). Educación Pearson. pag. 186.
11. Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Mass .: Addison-Wesley. ISBN 0-201-53082-1.
12. 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.
13. Grötschel, Martin ; László Lovász ; Alexander Schrijver (1988). "Complejidad, oráculos y computación numérica". Algoritmos geométricos y optimización combinatoria . Saltador. ISBN 0-387-13624-X.
14. Schrijver, Alexander (2003). "Preliminares sobre algoritmos y complejidad". Optimización combinatoria: poliedros y eficiencia . 1 . Saltador. ISBN 3-540-44389-4.
15. Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "Dureza ETH para subgrafo k mas 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áticas Industriales y Aplicadas. págs. 1326-1341. arXiv : 1504.08352 . doi : 10.1137 / 1.9781611974782.86 . Señor 3627815 . 
16. Complexity Zoo : Class QP: Quasipolynomial-Time
17. Impagliazzo, Russell ; Paturi, Ramamohan (2001). "Sobre la complejidad de k -SAT" (PDF) . Revista de Ciencias de la Computación y 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. Zoológico de complejidad : clase SUBEXP: tiempo subexponencial determinista
20. Moser, P. (2003). "Categorías de Baire en clases de pequeña complejidad". En Andrzej Lingas; 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 en Ciencias de la Computación . 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 Computación Aleatoria . Optimización combinatoria. Pub académico Kluwer. 9 : 843. doi : 10.1007 / 978-1-4615-0013-1_19 . ISBN 978-1-4613-4886-3.
22. Kuperberg, Greg (2005). "Un algoritmo cuántico de tiempo subexponencial para el problema del subgrupo oculto diedro". Revista SIAM de Computación . Filadelfia. 35 (1): 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 diedro con el espacio polinomial". arXiv : quant-ph / 0406151v1 .
24. Grohe, Martin; Neuen, Daniel (2021). "Avances recientes en el problema del isomorfismo gráfico". arXiv : 2011.01366 .
25. Flum, Jörg; Grohe, Martin (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 Sistemas . 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 . 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 del cuantificador para campos cerrados reales mediante descomposición algebraica cilíndrica". En Brakhage, H. (ed.). Teoría de los autómatas y lenguajes formales: 2da Conferencia GI, Kaiserslautern, 20-23 de mayo de 1975 . Apuntes de conferencias en Ciencias de la Computación. 33 . Saltador. págs. 134-183. doi : 10.1007 / 3-540-07407-4_17 . Señor 0403962 .