Complexidade de tempo

Em ciência da computação, a complexidade de tempo de um algoritmo quantifica a porção de tempo tomada por um algoritmo para rodar em função do tamanho da entrada do problema. A complexidade de tempo de um algoritmo é comumente expressada usando a notação big O, que suprime constantes multiplicativas e outros termos de menor ordem. Quando expressada dessa forma, a complexidade de tempo é descrita como assintótica, i.e., o tamanho da entrada tende ao infinito. Por exemplo, se o tempo requisitado por um algoritmo em todas as entradas de tamanho n é no máximo 5n³ + 3n, a assíntota da complexidade de tempo é O(n³).

Complexidade de tempo é comumente estimada pela contagem do número de operações elementares realizadas pelo algoritmo, onde a operação elementar toma a quantia fixa de tempo para realizar. A quantidade de tempo tomada e o número de operações elementares realizadas pelo algoritmo diferem no máximo de um fator constante.

Desde que o algoritmo deve tomar uma quantidade diferente de tempo mesmo dentro de entradas de mesmo tamanho, a medida mais comum de complexidade de tempo usada, o pior caso do algoritmo de complexidade de tempo, denotado T(n), é no máximo a quantidade de tempo usada numa entrada de tamanho n. A complexidade de tempo é classificada pela natureza da função T(n). Por exemplo, um algoritmo com T(n) = O(n) é chamado de algoritmo de tempo linear, e um algoritmo com T(n) = O(2ⁿ) é dito ser um algoritmo de tempo exponencial.

Tabela de complexidade de tempo comum

A tabela a seguir resume algumas classes de complexidade de tempo comumente usadas. Na tabela, poly(x) = x0(1), isto é, polinomial em X.

Nome	Classe de Complexidade	Tempo de execução (T(n))	Exemplos de tempo de execução	Exemplos de algoritmos
Tempo constante		O(1)	10	Determinando se o número é par ou ímpar
Função inversa de Ackermann		O(α(n))		Tempo amortizado por operação usando um conjunto dijunto
Logaritmo Iterativo		O(log-star(n) )		Algoritmo de Cole-Vishkin
log-logarítmico		O(log log n)		Tempo amortizado por operação usando uma fila de prioridades limitada ^[1]
Tempo logarítmico	DLOGTIME	O(log n)	log n, log(n²)	Busca binária
Tempo poli-logarítmico		poly(log n)	(log n)²
potência fracionária		O(n^c) onde 0 < c < 1	n^1/2, n^2/3	Procurando em uma kd-tree
Tempo linear		O(n)	n	Procurando o menor item em um array não ordenado
"n log star n"		O(nlog-star(n))		Algoritmo de triangulação de polígonos de Seidel.
Tempo linearitmico		O(n log n)	n log n, log n!	A ordenação por comparação mais rápida
Tempo quadrático		O(n²)	n²	Bubble sort; Insertion sort
Tempo cúbico		O(n³)	n³	Multiplicação ingênua de duas matrizes n×n. Calculando correlação parcial.
Tempo polinomial	P (classe de complexidade)	2^O(log n) = poly(n)	n, n log n, n¹⁰	Algoritmo de Karkamar para programação linear; Teste de primalidade de AKS
Tempo quasi-polinomial	QP	2^poly(log n)	n^log log n, n^log n	Melhor conhecido O(log² n)-algoritmo de aproximação para o problema da árvore de Steiner dirigida.
Tempo sub-exponencial (primeira definição)	SUBEXP	O(2^{n^ε}) para todos ε > 0	O(2^{log n^{log log n}})	Assumindo a complexidade do teorema de conjecturas, Polinômio probabilístico com limitação de erro está contido em um SUBEXP.^[2]
Tempo sux-exponencial (segunda definição)		2^o(n)	2^{n^1/3}	Melhor algoritmo conhecido para a fatoração de inteiros e isomorfismo em grafos
Tempo exponencial	E (classe de complexidade)	2^O(n)	1.1ⁿ, 10ⁿ	Resolvendo o problema do Caixeiro Viajante usando programação dinâmica
Tempo exponencial	EXPTIME	2^poly(n)	n!, nⁿ, 2^n²
Tempo fatorial		O(n!)	n!	Resolvendo o problema do caxeiro viajante via busca com força-bruta
Tempo duplamente exponencial	2-EXPTIME	2^{2^poly(n)}	2^3ⁿ	Decidindo a verdade de uma informação dada pela Aritmética de Presburger

Tempo Constante

Um algoritmo é dito ser em tempo constante (também escrito como executado em tempo O(1)) se o valor de T(n) é limitado por uma valor que não dependa do tamanho da entrada. Por exemplo, acessando um único elemento de um array usa tempo constante, visto que uma única operação foi executada para localizá-la. Encontrar o menor valor de um vetor não ordenado, contudo, não é uma operação de tempo constante, visto que é necessário olhar sobre todos os elementos do vetor para determinar qual é o menor valor de todos. Isto é, consequentemente, uma operação em tempo linear, em relação ao tamanho da entrada, utilizando tempo O(n). Se o número de elementos é conhecido posteriormente e não se altera, contudo, tal algoritmo pode ser dito que execute em tempo constante.

Apesar do nome "tempo constante", o tempo de execução pode não ser independente do tamanho da entrada, mas um limitante superior para o tempo de execução deve ser posto, independentemente do tamanho do problema. Por exemplo, a tarefa "trocar os valores de 'a' e 'b' tal que a=b" é dito como tempo tempo constante, mesmo que o tempo possa depender de que seja já verdade ou não que a = b. Existe uma constante t, contudo, tal que o tempo requerido seja, no máximo t.

Eis uns exemplos de trechos de códigos que rodam em tempo constante:

int index = 5;
int item = list[index];
se (condição verdadeira) então
   execute alguma operação que rode em tempo constante
senão
   execute alguma outra operação em tempo constante
para i = 1 até 100
   para j = 1 até 200
      execute alguma operação que rode em tempo constante.

Se T(n) é O(valor constante), isto é equivalente a ser dito como, na notação padrão que T(n) sendo O(1).

Tempo logarítmico

Um algoritmo é dito ter tempo logaritmo se T(n) = O(log n). Devido ao uso do sistema de números binários pelos computadores, o logaritmo é frequentemente de base 2 (isto é, log₂ n, muitas vezes escrito lg n). Contudo, pela troca da equação base para logaritmos, loga n and logb n diferem apenas por uma constante multiplicadora, porque na notação big-O é descartada; logo O(log n) é a notação padrão para algoritmos de tempo logaritmo independente da base do logaritmo.

Algoritmos que executam em tempo logarítmico são comumente encontrados em operações em árvores binárias ou quando se usa busca binária

Tempo Poli-logarítmico

Um algoritmo é dito rodar em tempo polilogaritmo se T(n) = O((log n)^k), para alguma constante k. Por exemplo, a ordenação de uma cadeia de matrizes pode ser resolvida em tempo poli-logarítmico em uma máquina paralela de acesso aleatório.

Tempo sub-linear

Um algoritmo é dito rodar em tempo sub-linear (frequentemente chamado tempo sublinear) se T(n) = o(n). Particularmente isso inclui algoritmos com complexidade de tempo definida acima, também tal como o O(n½) algoritmo de busca de Grover.

Para um algoritmo ser exato e ainda rodar em tempo sub-linear, é necessário usar processamento paralelo (como o cálculo de determinante de matrizes NC1 faz) ou processamento não-clássico (como a busca de Grover faz), ou alternativamente ter garantido uma suposição na estrutura da entrada (como a busca binária de tempo logaritmo e algoritmos de manuntenção de muitas árvores faz). Caso contrário, um algoritmo de tempo sub-linear não poderia ler ou aprender previamente toda a entrada para prover sua saída.

O termo específico algoritmo de tempo sublinear é usualmente reservado para algoritmos que são diferentes dos acimas uma vez que eles rodam sobre uma máquina serial clássica e não é permitido previamente supor a entrada.^[3] Eles são, contudo, passíveis de serem aleatorizados e, claramente, serão para todos, exceto nos casos mais triviais.

Eles, no entanto, são permitidos se randomizarem, e de fato precisam ser randomizados para tudo mas a maioria são tarefas triviais. Um algoritmo precisa prover uma resposta sem ler toda a entrada, isso é particularmente difícil dependendo do acesso permitido a entrada. Usualmente para uma entrada que é representada como uma string binária b1,...,bk é assumido que o algoritmo possa, em tempo O(1), pedir e obter o valor de bi para qualquer i.

Algoritmos de tempo sublinear são tipicamente aleatórios e provêm apenas aproximações da solução. De fato, a propriedade de string binários que contêm apenas zeros (e nenhum uns) pode ser facilmente mostrada que não é decídivel por um algoritmo (não-aproximado) de tempo sublinear. Algoritmos de tempo sublinear naturalmente surgem na investigação de teste de prioridade.

Tempo linear

Um algoritmo é dito que usa tempo linear, ou tempo O(n), se sua complexidade de tempo é O(n). Informalmente, isto significa que para entradas grandes o suficiente o tempo de execução delas aumenta linearmente com o tamanho da entrada. Por exemplo, um procedimento que adiciona todos os elementos em uma lista requere tempo proporcional ao tamanho da lista. Esta descrição é levemente imprecisa, visto que o tempo de execução pode desviar significantemente de uma proporção precisa, especialmente para valores pequenos de n.

Tempo linear é comumente visto como um atributo desejável para um algoritmo. Muitas pesquisas foram investidas na criação de algoritmos exibindo (próximos a) tempos lineares ou melhores. Esta pesquisa inclui tanto abordagens de software como hardware. No caso de hardware, alguns algoritmos que, matematicamente falando, pode nunca alcançar tempo linear com os modelos de computação comum são aptos a rodar em tempo linear. Existem várias tecnologias de hardware que exploram paralelismo para prover isto. Um exemplo disto é memória de conteúdo endereçável. Este conceito de linearidade de tempo é usado em algoritmos de emparelhamento de strings tais como o algoritmo de Boyer-Moore e o algoritmo de Ukkonen.

Tempo Linearitmico/quasilinear

Uma função linearitmica (conjunção de linear e logarítmica) é uma função do formato n . log n (isto é, um produto de termos lineares e logarítmicos). Um algoritmo é dito executar em tempo linearitmico se T(n) = O(n log n). Comparada a outras funções, uma função linearítmica é ω(n), o(n^1+ε) para todo ε > 0 e Θ(n · log n). Um termo linearítmico cresce mais rápido que um termo linear, mas mais devagar que algum polinômio em n com expoente estritamente maior que 1.

Um algoritmo é dito executar em tempo quasilinear se T(n) = O(n logk n) para alguma constante k. Algoritmos de tempo qualisnear também são o(n^1+ε) para todo ε > 0 e, portanto, executa mais rápido que um polinômio em n com expoente estritamente maior que 1.

Em muitos casos, o tempo de execução n . log n é simplesmente o resultado de executar T(log n) operações n vezes. Por exemplo, ordenação por árvores binárias cria uma árvore binária ao inserir cada elemento do vetor de tamanho n em cada vez. Visto que a operação de inserção em uma árvore binária de busca utiliza tempo O(log n), todo o algoritmo usa tempo linearitmico.

Ordenação de comparações requere ao menor uma quantidade de operações linearítmicas no pior caso, pois log(n!) = T(n log n), pela aproximação de Stirling. Eles aparecem frequentemente na relação de recorrência T(n) = 2 * T(n/2) + O(n).

Alguns algoritmos que executam em tempo linearitmico incluem:

Comb sort, no caso médio e pior caso
Quicksort no caso médio
Heapsort, Merge sort, introsort, ordenação por árvore binária, smoothsort, patience sorting, etc. no pior caso
Transformada Rápida de Fourier
Cálculo do array de Monge

Tempo subquadrático

Um algoritmo é dito subquadrático se T(n) = o(n²).

Por exemplo, a maioria dos algoritmos baseados em comparações ingênuas são quadráticos (por exemplo insertion sort), mais algoritmos mais avançados que são encontrados são subquadráticos (por exemplo shell sort). Nenhum tipo de ordenação com intúitos gerais roda em tempo linear, mas a mudança de quadrático para subquadrático é de grande importância prática.

Tempo Polinomial

Um algoritmo é dito ser de tempo polinomial se o tempo de execução dele é limitado superiormente por uma expressão polinomial do tamanho da entrada para o algoritmo, T(n) = O(n^k) para algumas constantes k. [5][6] Problemas para algoritmos de tempo polinomial existem pertencendo a classe de complexidade P, que é central no campo da teoria da complexidade computacional. A tese de Bobham afirma que tempo polinomial é um sinônimo para "dócil", "viável", "eficiente", ou "veloz". [7]

Alguns exemplos de algoritmos de tempo polinomial:

O algoritmo de ordenação quicksort em n inteiros executa, no máximo, An² operações para algumas constantes A. Assim, é executado em tempo O (n²) e é um algoritmo de tempo polinomial.
Todas as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) pode ser feito em tempo polinomial.
Emparelhamento máximo em grafos podem ser encontrados em tempo polinomial.

Tempo forte e fracamente polinomial

Em alguns contextos, especialmente em otimização, existe uma diferença entre o tempo fortemente polinomial e algoritmos de tempo fracamente polinomial. Estes dois conceitos são relevantes apenas se as entradas para os algoritmos consistem de inteiros.

Tempo fortemente polinomial é definido no modelo aritmético de computação. Neste modelo de cálculo as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) dão um passo na unidade de tempo para realizar, independentemente do tamanho dos operandos. O algoritmo é executado em tempo fortemente polinomial se ^[4]

o número de operações aritméticas no modelo de computação é limitado por um polinômio com número de inteiros na instância de entrada; e
o espaço usado pelo algoritmo é limitado por um polinômio do tamanho da entrada.

Qualquer algoritmo com essas duas propriedades podem ser convertidos para um algoritmo de tempo polinomial, substituindo as operações aritméticas por algoritmos adequados para realizar as operações aritméticas em uma máquina de Turing. Se o segundo do requisito acima não for satisfeito, então este não é mais verdadeiro. Dado o inteiro 2n (que ocupa um espaço proporcional ao n), é possível calcular com n multiplicações usando quadratura repetida. No entanto, o espaço usado para representar é proporcional a 2n, e, assim, exponencial ao invés de polinomial no espaço usado para representar a entrada. Por isso, não é possível realizar este cálculo em tempo polinomial em uma máquina de Turing, mas é possível calcular que pelas muitas operações aritméticas polinomialmente.

Existem algoritmos que executam em tempo polinomial no modelo de máquina de Turing, mas não no modelo de aritmética. O algoritmo de Euclides para calcular o máximo divisor comum de dois inteiros é um exemplo. Dados dois inteiros a e b o tempo de execução do algoritmo é limitado por. Este é polinomial do tamanho de uma representação binária de a e b como o tamanho de uma tal representação é mais ou menos. No entanto, o algoritmo não é executado em tempo fortemente polinomial como o tempo de execução depende da magnitude de a e b, e não apenas no número de inteiros na entrada (que é constante neste caso, há sempre apenas dois números inteiros na entrada).

Um algoritmo que é executado em tempo polinomial, mas que não é fortemente polinomial é dito para ser executado em um tempo fracamente polinomial. [9] Um exemplo bem conhecido de um problema para o qual um algoritmo de tempo fracamente polinomial é conhecido, mas não é conhecido para admitir um algoritmo em tempo fortemente polinomial, é a programação linear. Tempo fracamente polinomial não deve ser confundido com tempo pseudo-polinomial.

Classes de Complexidade

O conceito de tempo polinomial leva a várias classes de complexidade na teoria da complexidade computacional. Algumas classes importantes definidas usando tempo polinomial são as seguintes:

P: A classe de complexidade dos problemas de decisão que podem ser resolvidos em uma máquina de Turing determinística em tempo polinomial.
NP: A classe de complexidade dos problemas de decisão que podem ser resolvidos em uma máquina de Turing não-determinística em tempo polinomial.
ZPP: A classe de complexidade dos problemas de decisão que podem ser resolvidos com erro zero em uma máquina de Turing probabilística em tempo polinomial.
RP: A classe de complexidade dos problemas decisão que podem ser resolvidos com 1 lado de erro em uma máquina de Turing probabilística em tempo polinomial.
BPP: A classe de complexidade dos problemas de decisão que podem ser resolvidos com 2 lados de erro em uma máquina de Turing probabilística em tempo polinomial.
BQP:A classe de complexidade dos problemas de decisão que podem ser resolvidos com 2 lados de erro em uma máquina de Turing quântica em tempo polinomial.

P é o menor classe de complexidade de tempo em uma máquina determinística, que é robusta em termos de mudanças no modelo da máquina. (Por exemplo, uma mudança de uma máquina de Turing única fita para uma máquina multi-fita pode levar a um aumento de velocidade quadrática, mas qualquer algoritmo que é executado em tempo polinomial em um modelo também faz isso no outro.) Qualquer máquina abstrata terá uma classe de complexidade correspondente aos problemas que podem ser resolvidos em tempo polinomial em sua máquina.

Tempo superpolinomial

Um algoritmo é dito que utiliza tempo superpolinomial se T(n) não limitante superiormente por nenhum polinômio. Ele utiliza tempo ω(n^c) para todas as constantes c, onde n é o parâmetro de entrada, tipicamente o número de bits da entrada.

Por exemplo, um algoritmo que tida por ( ... ) passos em uma entrada de tamanho n requere tempo superpolinomial (mais especificamente, tempo exponencial).

Um algoritmo que usa recursos exponenciais é claramente superpolinomial, mas alguns algoritmos são só fracamente superpolinomiais. Por exemplo, o teste de primalidade de Adleman-Pomerance-Rumely roda em tempo n^{O(log log n)} em entrda de n bits; isto cresce mais rápido que qualquer outro polinômio com n grande o suficiente, mas o tamanho da entrada deve se tornar impraticavelmente grande antes de não ser dominado por um polinômio de grau pequeno.

Um algoritmo que fora provado que requere tempo superpolinomial não pode ser resolvido em tempo polinomial, e logo é conhecido como estando fora da classe de complexidade P. A tese de Cobham conjectura que estes algoritmos são impraticáveis e, em muitos casos, eles são. Visto que o problema P versus NP não fora resolvido, nenhum algoritmo de um problema NP-Completo é conhecido atualmente para rodar em tempo polinomial.

Tempo quasi-polinomial

Algoritmos de tempo quasi-polinomiais são algoritmos que rodar em tempo mais devagar que tempo polinomial, ainda que não seja tão lento para ser considerado de tempo exponencial. O pior caso de tempo de execução de um algoritmo de tempo quasi-polinomial é $2^{O((\log n)^{c})}$ para algum c fixado. O algoritmo clássico e mais conhecido para fatoração de inteiros, o crivo de campo para números gerais, que roda tempo $2^{{\tilde {O}}(n^{1/3})}$ não é um algoritmo de tempo quasi-polinomial, visto que o tempo de execução não pode ser expresso como $2^{O((\log n)^{c})}$ para algum c fixo. Se a constante "c", na definição de quasi-polinomial é igual a 1, possuiremos um algoritmo de tempo linear, e se form menor que 1, possuiremos um algoritmo de tempo sublinear.

Algoritmos de tempo quali-polinomial surgem tipicamente de reduções de um problema NP-difícil para outro. Por exemplo, um problema pode pegar uma instância de um problema NP-difícil, digamos 3-SAT, e o convertemos para uma instância de outro problema B, mas o tamanho da instância se torna $2^{O((\log n)^{c})}$ . Neste caso, a redução não prova que o problema B é NP-difícil; esta redução apenas mostra que não existe nenhum algoritmo em tempo polinomial para B ao menos que exista um algoritmo de tempo quasi-polinomial para 3-SAT (e, portanto, tudo de NP). De forma análoda, existem problemas os quais conhecemos algoritmos de tempo quasi-polinomiais, mas não existindo nenhum algoritmo de tempo polinomial conhecido. Tais problemas surgem em algoritmos de aproximação; um exemplo famoso destes é o problema da árvore de Steiner dirigida, o qual existe um algoritmo de aproximação de tempo quasi-polinomial alcançando um fator de O(log2n) (n sendo o número de vértices), mas mostrando que a existência de um algoritmo em tempo polinomail é um problema em aberto.

A classe de complexidade QP consiste em todos os problemas que possuem algoritmos de tempo quasi-polinomial. Pode ser definido em termos de DTIME em.

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

Relação a problemas NP-Completos

Na teoria da complexidade, o problema não resolvido P versus NP pergunta se todos problemas em NP possuem algoritmos de tempo polinomial. Todos os algoritmos mais conhecidos para algoritmos de problemas NP-completos como 3-SAT, etc. utilizam tempo exponencial. Aqui, "tempo sub-exponencial" é dito para responder à segunda definição descrita acima. (Em outro lado, vários problemas de grafos representados na maneira natural de matrizes de adjacências são resolvíveis em tempo sub-expoencial simplesmente por que o tamanho da entrada é o quadrado do número de vértices.) Esta conjectura (para o problema k-SAT) é conhecido pela hipótese de tempo exponencial [11]. Visto que é conjecturado que problemas NP-completos não possuem algoritmos de tempo quasi-polinomiais, alguns resultados não-aproximados no campo de algoritmos de aproximação assumem que problemas NP-completos não possuem algoritmos de tempo quasi-polinomiais. Por exemplo, veja os resultados não-aproximados para o problema de cobertura de conjuntos.

Tempo Sub-exponencial

O termo tempo sub-exponencial é usado para expressar que o tempo de execução de algum algoritmo pode crescer mais rápido do que qualquer polinômio, mas ainda é significativamente menor do que uma exponencial. Neste sentido, problemas que têm algoritmos de tempo sub-exponenciais são um pouco mais dóceis do que aqueles que só têm algoritmos exponenciais. A definição precisa de "sub-exponencial" não é geralmente acordada, [12] e listamos os dois mais amplamente utilizado abaixo.

Primeira definição

Um problema é dito ser resolvível em tempo sub-exponencial, se ele pode ser resolvido em tempos de execução, cujos logaritmos crescem menos do que qualquer polinômio dado. Mais precisamente, um problema está em tempo sub-exponencial, se para cada ε > 0 existe um algoritmo que resolve o problema em tempo O(2^{n^ε}). O conjunto de todos esses problemas é a classe de complexidade SUBEXP, que pode ser definida em termos de DTIME como se segue.^[2]^[5]^[6]

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

Note que esta noção de sub-exponencial não é uniforme em termos de ε no sentido de que ε não é parte da entrada e cada ε pode ter seu próprio algoritmo para o problema.

Segunda definição

Alguns autores definem tempo sub-exponencial como rodar vezes em 2^o(n).^[7]^[8] Esta definição permite maiores tempos de execução do que a primeira definição de tempo sub-exponencial. Um exemplo de tal algoritmo vez que um sub-exponencial é o algoritmo mais conhecido clássico para fatoração de inteiros, a crivo do campo de número geral, que é executado em tempo sobre $2^{{\tilde {O}}(n^{1/3})}$ , onde o comprimento da entrada é n. Outro exemplo é o algoritmo mais conhecido para o problema de isomorfismo de grafos, que roda em tempo 2^{O(√(n log n))}.

Note que isso faz diferença se o algoritmo é permitido ser sub-exponencial no tamanho da instância, o número de vértices, ou o número de arestas. Quanto a complexidade parametrizada, esta diferença é explicitada por pares, considerando $(L,k)$ de problemas de decisão e parâmetros k. SUBEPT é a classe de todos os problemas parametrizados que são executados em tempo sub-exponencial k e polinomial do tamanho da entrada n:^[9]

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right)

.

Mais precisamente, SUBEPT é a classe de todos os problemas parametrizados $(L,k)$ para os quais há uma função computável $f:\mathbb {N} \to \mathbb {N}$ que $f\in o(k)$ e um algoritmo que decide L em tempo $2^{f(k)}\cdot {\text{poly}}(n)$ .

Hipótese de tempo exponencial

A hipótese de tempo exponencial (ETH) é que 3SAT, o problema satisfatibilidade de fórmulas booleanas em forma normal conjuntiva com no máximo três literais por cláusula e com n variáveis, não podem ser resolvidas em tempo 2^o(n). Mais precisamente, a hipótese é que existe alguma constante absoluta c>0 tais como 3SAT que não pode ser decidida em tempo 2^cn por qualquer máquina de Turing determinística. Com m denotando o número de cláusulas, ETH é equivalente à hipótese de quekSAT não pode ser resolvido em tempo 2^o(m) para qualquer inteiro k≥3.^[10] A hipótese de tempo exponencial implica P ≠ NP.

Tempo exponencial

Um algoritmo é dito ser tempo exponencial, T se( n) é superiormente limitada por 2^poly(n), onde poly(n) é algum polinômio em n. Mais formalmente, um algoritmo é exponencial se o tempo T(n) é limitado por O(2^{n^k}) para algumas constantes k. Problemas que admitem algoritmos de tempo exponencial em uma máquina de Turing determinística formam a classe de complexidade conhecido como EXP.

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

Às vezes, o tempo exponencial é usado para se referir aos algoritmos que T(n) = 2^O(n),onde o expoente é, no máximo, uma função linear den. Isto dá origem à classe de complexidade E.

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

Tempo duplamente exponencial

Um algoritmo é dito ser de tempo exponencial duplo se T(n) é limitado superiormente por 2^{2^poly(n)}, onde poly(n) é algum polinômio em n. Esses algoritmos pertencem à classe de complexidade 2-EXPTIME.

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

Bem conhecidos algoritmos de tempo duplamente exponencial incluem:

Procedimentos de decisão para aritmética de Presburger
Computando a base de Gröbner (no pior caso)
Eliminação de quanitifadores em campos reais fechados leva pelo menos duplamente tempo exponencial (mas não é ainda conhecido por ser computável em ELEMENTARY)

Veja também

L-NOTATION

Referências

↑ Mehlhorn, Kurt; Naher, Stefan (1990). «Bounded ordered dictionaries in O(log log N) time and O(n) space». Information Processing Letters
↑ ^a ^b Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). «BPP has subexponential time simulations unless EXPTIME has publishable proofs». Berlin, New York: Springer-Verlag. Computational Complexity. 3 (4): 307–318. doi:10.1007/BF01275486
↑ Kumar, Ravi; Rubinfeld, Ronitt (2003). «Sublinear time algorithms» (PDF). SIGACT News. 34 (4): 57–67
↑ Grötschel, Martin; László Lovász, Alexander Schrijver (1988). «Complexity, Oracles, and Numerical Computation». Geometric Algorithms and Combinatorial Optimization. [S.l.]: Springer. ISBN 038713624X
↑ Moser, P. (2003). «Baire's Categories on Small Complexity Classes». Berlin, New York: Springer-Verlag. Lecture Notes in Computer Science: 333–342. ISSN 0302-9743
↑ Miltersen, P.B. (2001). «DERANDOMIZING COMPLEXITY CLASSES». Kluwer Academic Pub. Handbook of Randomized Computing: 843
↑ Kuperberg, Greg (2005). «A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem». Philadelphia: Society for Industrial and Applied Mathematics. SIAM Journal on Computing. 35 (1): 188. ISSN 1095-7111
↑ Oded Regev (2004). «A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space». arXiv:quant-ph/0406151v1 [quant-ph]
↑ Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. [S.l.]: Springer. p. 417. ISBN 978-3-540-29952-3. Consultado em 5 de março de 2010
↑ 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

[1] Mehlhorn, Kurt; Naher, Stefan (1990). «Bounded ordered dictionaries in O(log log N) time and O(n) space». Information Processing Letters

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

[3] Kumar, Ravi; Rubinfeld, Ronitt (2003). «Sublinear time algorithms» (PDF). SIGACT News. 34 (4): 57–67

[4] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). «Complexity, Oracles, and Numerical Computation». Geometric Algorithms and Combinatorial Optimization. [S.l.]: Springer. ISBN 038713624X

[5] Moser, P. (2003). «Baire's Categories on Small Complexity Classes». Berlin, New York: Springer-Verlag. Lecture Notes in Computer Science: 333–342. ISSN 0302-9743

[6] Miltersen, P.B. (2001). «DERANDOMIZING COMPLEXITY CLASSES». Kluwer Academic Pub. Handbook of Randomized Computing: 843

[7] Kuperberg, Greg (2005). «A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem». Philadelphia: Society for Industrial and Applied Mathematics. SIAM Journal on Computing. 35 (1): 188. ISSN 1095-7111

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

[9] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. [S.l.]: Springer. p. 417. ISBN 978-3-540-29952-3. Consultado em 5 de março de 2010

[10] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]