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 no suele ser 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 del 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 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 de tiempoes un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo por alguna constante es un algoritmo de tiempo polinomial .
Tabla de complejidades temporales comunes
La siguiente tabla resume algunas clases de complejidades temporales que se encuentran comúnmente. En la tabla, 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
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, que toma 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
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, dondedenota la función de piso . Si, entonces hemos terminado. De lo contrario, si, 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 3 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 sublineal usan procesamiento paralelo (como lo hace el cálculo determinante de la matriz NC 1 ), 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 1 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 sublineal.
El término específico algoritmo de tiempo sublineal generalmente se reserva para algoritmos que son diferentes a los anteriores, ya 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 1 ,…, 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 ( 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 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 2 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 2 ) .
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á delimitado 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 . La tesis de Cobham establece que el tiempo polinomial es sinónimo de "manejable", "factible", "eficiente" o "rápido". [12]
Algunos ejemplos de algoritmos de tiempo polinomial:
- El algoritmo de ordenación de clasificación de selección en n enteros realizaoperaciones para alguna constante A . Así corre en el tiempo y es un algoritmo de tiempo polinomial.
- Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinomial.
- 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]
- 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
- 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 entero(que ocupa un espacio proporcional an en el modelo de la máquina de Turing), es posible calcularcon n multiplicaciones usando el cuadrado repetido . Sin embargo, el espacio utilizado para representar es proporcional a , 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 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 ejecución real depende de las magnitudes de y 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 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 mediante 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 poco 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 n 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-polinomial es para algunos arreglados . Para obtenemos un algoritmo de tiempo polinomial, para obtenemos un algoritmo de tiempo sublineal.
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 se vuelve. 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 problema del árbol de Steiner dirigido , para el cual existe un algoritmo de aproximación de tiempo cuasi-polinomial que logra un factor de aproximación de( siendo n el número de vértices), pero mostrar la existencia de tal algoritmo de tiempo polinomial es un problema abierto.
Otros problemas computacionales con soluciones de tiempo cuasi-polinomiales pero sin solución de tiempo polinomial conocida incluyen el problema de la camarilla plantada en el que el objetivo es encontrar una camarilla grande en la unión de una camarilla y un gráfico aleatorio . Aunque 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 una suposición 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]
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 inapropiabilidad 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 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]
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 un 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 el algoritmo más conocido de 1982 a 2016 resolvió en. Sin embargo, en STOC 2016 se presentó un algoritmo de tiempo cuasi-polinomial. [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 complejidad parametrizada , esta diferencia se hace explícita al considerar paresde 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]
Más precisamente, SUBEPT es la clase de todos los problemas parametrizados para lo cual hay una función computable con y un algoritmo que decide L a tiempo.
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 .
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 .
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 doble tiempo exponencial 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 .
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
- Algoritmos de intercambio de bloques
- Notación L
- Complejidad espacial
Referencias
- ↑ a b Sipser, Michael (2006). Introducción a la Teoría de la Computación . ISBN de Course Technology Inc. 0-619-21764-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 .
- ^ 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 .
- ^ Lenstra, Jr., HW ; Pomerance, Carl (11 de diciembre de 2016). "Prueba de primalidad con períodos gaussianos" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b 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 .
- ^ Bradford, Phillip G .; Rawlins, Gregory JE; Shannon, Gregory E. (1998). "Orden de cadena de matriz eficiente en tiempo Polylog". Revista SIAM de Computación . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas . 27 (2): 466–490. doi : 10.1137 / S0097539794270698 . ISSN 1095-7111 .
- ^ Holm, Jacob; Rotenberg, Eva (2020). "Prueba de planaridad totalmente dinámica en tiempo polilogarítmico" . STOC 2020 : 167–180. arXiv : 1911.03449 . doi : 10.1145 / 3357713.3384249 .
- ^ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Algoritmos de tiempo sublineal" (PDF) . Noticias SIGACT . 34 (4): 57–67. doi : 10.1145 / 954092.954103 .
- ^ 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 . Consultado el 23 de febrero de 2015 .
- ^ Sedgewick, R. y Wayne K (2011). Algoritmos, 4ª Ed . pag. 186. Pearson Education, Inc.
- ^ Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Mass .: Addison-Wesley. ISBN 0-201-53082-1.
- ^ Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, metodología y filosofía de la ciencia II . Holanda Septentrional.
- ^ 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.
- ^ Schrijver, Alexander (2003). "Preliminares sobre algoritmos y complejidad". Optimización combinatoria: poliedros y eficiencia . 1 . Saltador. ISBN 3-540-44389-4.
- ^ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), Dureza ETH para el subgráfico k más denso con perfecta integridad , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B.
- ↑ Complexity Zoo : Class QP: Quasipolynomial-Time
- ^ a b Impagliazzo, R .; Paturi, R. (2001). "Sobre la complejidad de k-SAT". Revista de Ciencias de la Computación y Sistemas . Elsevier . 62 (2): 367–375. doi : 10.1006 / jcss.2000.1727 . ISSN 1090-2724 .
- ^ Aaronson, Scott (5 de abril de 2009). "Un dilema no del todo exponencial" . Optimizado para Shtetl . Consultado el 2 de diciembre de 2009 .
- ^ Zoológico de complejidad : clase SUBEXP: tiempo subexponencial determinista
- ^ 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 informática . 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 .
- ^ 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.
- ^ 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 .
- ^ Oded Regev (2004). "Un algoritmo de tiempo subexponencial para el problema del subgrupo oculto diedro con el espacio polinomial". arXiv : quant-ph / 0406151v1 .
- ^ Grohe, Martin; Neuen, Daniel (2021). "Avances recientes en el problema del isomorfismo gráfico". arXiv : 2011.01366 . Cite journal requiere
|journal=
( ayuda ) - ^ Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Saltador. pag. 417. ISBN 978-3-540-29952-3.
- ^ Impagliazzo, R .; Paturi, R .; Zane, F. (2001). "¿Qué problemas tienen una complejidad fuertemente exponencial?". Revista de Ciencias de la Computación y Sistemas . 63 (4): 512–530. doi : 10.1006 / jcss.2001.1774 .
- ^ Mayr, E. y Mayer, A .: La complejidad del problema verbal para semigrupos conmutativos e ideales polinomiales. Adv. Matemáticas. 46 (1982) págs. 305–329
- ^ JH Davenport y J. Heintz: La eliminación del cuantificador real es doblemente exponencial. J. Symbolic Comp. 5 (1988) págs. 29–35.
- ^ GE Collins: Eliminación del cuantificador para campos cerrados reales mediante descomposición algebraica cilíndrica. Proc. 2do. Conferencia GI Teoría de autómatas y lenguajes formales (Springer Lecture Notes in Computer Science 33) págs. 134–183