Complexidade de tempo

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar
Gráficos de funções comumente usadas na análise de algoritmos , mostrando o número de operações N como resultado do tamanho da entrada n para cada função

Na ciência da computação , a complexidade de tempo é a complexidade computacional que descreve a quantidade de tempo do computador que leva para executar um algoritmo . A complexidade de tempo é comumente estimada pela contagem do número de operações elementares executadas pelo algoritmo, supondo que cada operação elementar leve um tempo fixo para ser executada. Assim, a quantidade de tempo gasto e o número de operações elementares executadas pelo algoritmo são considerados relacionados por um fator constante .

Como o tempo de execução de um algoritmo pode variar entre diferentes entradas de mesmo tamanho, geralmente considera -se a complexidade de tempo do pior caso , que é a quantidade máxima de tempo necessária para entradas de um determinado tamanho. Menos comum, e geralmente especificada explicitamente, é a complexidade de caso médio , que é a média do tempo gasto em entradas de um determinado tamanho (isso faz sentido porque há apenas um número finito de entradas possíveis de um determinado tamanho). Em ambos os casos, a complexidade de tempo é geralmente expressa em função do tamanho da entrada. [1] : 226 Como essa função geralmente é difícil de calcular exatamente, e o tempo de execução para pequenas entradas geralmente não é conseqüente, geralmente se concentra no comportamento da complexidade quando o tamanho da entrada aumenta - ou seja, o comportamento assintótico da complexidade. Portanto, a complexidade de tempo é comumente expressa usando notação O grande , normalmente, , , , etc., onde n é o tamanho em unidades de bits necessários para representar a entrada.

As complexidades algorítmicas são classificadas de acordo com o tipo de função que aparece na notação O grande. Por exemplo, um algoritmo com complexidade de tempoé um algoritmo de tempo linear e um algoritmo com complexidade de tempopara alguma constanteé um algoritmo de tempo polinomial .

Tabela de complexidades de tempo comuns

A tabela a seguir resume algumas classes de complexidades de tempo comumente encontradas. Na tabela, poli( x ) = x O (1) , ou seja, polinômio em  x .

Nome Classe de complexidade Tempo de execução ( T ( n ) ) Exemplos de tempos de execução Algoritmos de exemplo
tempo constante 10 Encontrando o valor mediano em uma matriz ordenada de números

Calculando (−1) n

tempo de Ackermann inverso Tempo amortizado por operação usando um conjunto disjunto
tempo logarítmico iterado Coloração distribuída de ciclos
logarítmico Tempo amortizado por operação usando uma fila de prioridade limitada [2]
tempo logarítmico DLOGTIME , Pesquisa binária
tempo polilogarítmico
potência fracionária Onde , Procurando em uma árvore kd
tempo linear n , Encontrar o menor ou o maior item em uma matriz não classificada , algoritmo de Kadane , pesquisa linear
"n log-star n" hora Algoritmo de triangulação de polígonos de Seidel .
tempo linearítmico , Ordenação de comparação mais rápida possível ; Transformada rápida de Fourier .
tempo quase linear
tempo quadrático Ordenação de bolhas ; Ordenação por inserção ; Convolução direta
tempo cúbico Multiplicação ingênua de doismatrizes. Calculando a correlação parcial .
tempo polinomial P , algoritmo de Karmarkar para programação linear ; Teste de primalidade AKS [3] [4]
tempo quase polinomial QP , Algoritmo de aproximação O ( log 2 n ) mais conhecido para o problema de árvore de Steiner dirigido .
tempo subexponencial
(primeira definição)
SUBEXP para todos Contém BPP a menos que EXPTIME (veja abaixo) seja igual a MA . [5]
tempo subexponencial
(segunda definição)
Algoritmo mais conhecido para fatoração de inteiros ; anteriormente o melhor algoritmo para isomorfismo de grafos
tempo exponencial
(com expoente linear)
E , Resolvendo o problema do caixeiro viajante usando programação dinâmica
tempo exponencial EXPTIME , Resolvendo a multiplicação da cadeia de matrizes por meio de pesquisa de força bruta
tempo fatorial Resolvendo o problema do caixeiro viajante por meio de busca de força bruta
tempo exponencial duplo 2-EXPTIME Decidindo a verdade de uma dada afirmação na aritmética de Presburger

Tempo constante

Diz-se que um algoritmo é de tempo constante (também escrito comotempo) se o valor deé limitado por um valor que não depende do tamanho da entrada. Por exemplo, acessar qualquer elemento único em uma matriz leva um tempo constante, pois apenas uma operação precisa ser executada para localizá-lo. De maneira semelhante, encontrando o valor mínimo em uma matriz classificada em ordem crescente; é o primeiro elemento. No entanto, encontrar o valor mínimo em uma matriz não ordenada não é uma operação de tempo constante, pois a varredura de cada elemento na matriz é necessária para determinar o valor mínimo. Portanto, é uma operação de tempo linear, tomandoTempo. Se o número de elementos é conhecido antecipadamente e não muda, no entanto, tal algoritmo ainda pode ser dito para ser executado em tempo constante.

Apesar do nome "tempo constante", o tempo de execução não precisa ser independente do tamanho do problema, mas um limite superior para o tempo de execução deve ser independente do tamanho do problema. Por exemplo, a tarefa "trocar os valores de a e b se necessário para queé chamado de tempo constante, embora o tempo possa depender se já é ou não verdade que. No entanto, existe alguma constante t tal que o tempo necessário é sempre no máximo t .

Aqui estão alguns exemplos de fragmentos de código que são executados em tempo constante:

int índice = 5;
int item = lista[índice];
se (condição verdadeira) então
    realizar alguma operação que é executada em tempo constante
senão
    executar alguma outra operação que é executada em tempo constante
para i = 1 a 100
     para j = 1 a 200
        realizar alguma operação que é executada em tempo constante

Seé, onde a é qualquer valor constante, isso é equivalente e indicado em notação padrão comoser.

Tempo logarítmico

Diz-se que um algoritmo leva tempo logarítmico quando. Desdeeestão relacionados por um multiplicador constante , e tal multiplicador é irrelevante para a classificação O grande, o uso padrão para algoritmos de tempo logarítmico éindependentemente da base do logaritmo que aparece na expressão de T .

Algoritmos que levam tempo logarítmico são comumente encontrados em operações em árvores binárias ou ao usar busca binária .

Umalgoritmo é considerado altamente eficiente, pois a razão entre o número de operações e o tamanho da entrada diminui e tende a zero quando n aumenta. Um algoritmo que deve acessar todos os elementos de sua entrada não pode tomar tempo logarítmico, pois o tempo gasto para ler uma entrada de tamanho n é da ordem de n .

Um exemplo de tempo logarítmico é dado pela pesquisa de dicionário. Considere um dicionário D que contém n entradas, ordenadas por ordem alfabética . Suponhamos que, para, pode-se acessar a k - ésima entrada do dicionário em um tempo constante. Deixardenotar esta k - ésima entrada. Sob essas hipóteses, o teste para ver se uma palavra w está no dicionário pode ser feito em tempo logarítmico: considere, Ondedenota a função chão . Se, então terminamos. Caso contrário, se, continue a pesquisa da mesma forma na metade esquerda do dicionário, caso contrário, continue da mesma forma com a metade direita do dicionário. Esse algoritmo é semelhante ao método frequentemente usado para encontrar uma entrada em um dicionário de papel.

Tempo polilogarítmico

Diz-se que um algoritmo é executado em tempo polilogarítmico se seu tempoépara alguma constante k . Outra maneira de escrever isso é.

Por exemplo, a ordenação da cadeia de matrizes pode ser resolvida em tempo polilogarítmico em uma máquina paralela de acesso aleatório [6] e um grafo pode ser determinado como planar de uma maneira totalmente dinâmica emtempo por operação de inserção/exclusão. [7]

Tempo sublinear

Diz-se que um algoritmo é executado em tempo sublinear (frequentemente escrito tempo sublinear ) se. Em particular, isso inclui algoritmos com as complexidades de tempo definidas acima.

Algoritmos típicos que são exatos e ainda executados em tempo sublinear usam processamento paralelo (como o cálculo do determinante da matriz NC 1 faz), ou alternativamente têm suposições garantidas na estrutura de entrada (como a busca binária de tempo logarítmico e muitos algoritmos de manutenção de árvore fazem) . No entanto, linguagens formais como o conjunto de todas as strings que possuem 1 bit na posição indicada pelo primeirobits da string podem depender de cada bit da entrada e ainda ser computáveis ​​em tempo sublinear.

O termo específico algoritmo de tempo sublinear é geralmente reservado para algoritmos que são diferentes dos anteriores, pois são executados em modelos clássicos de máquinas seriais e não são permitidos pressupostos prévios na entrada. [8] No entanto, eles podem ser randomizados e, de fato, devem ser randomizados para todas as tarefas, exceto as mais triviais.

Como tal algoritmo deve fornecer uma resposta sem ler toda a entrada, suas particularidades dependem muito do acesso permitido à entrada. Normalmente para uma entrada que é representada como uma string bináriaassume-se que o algoritmo pode com o temposolicite e obtenha o valor depara qualquer i .

Os algoritmos de tempo sublinear são geralmente aleatórios e fornecem apenas soluções aproximadas . De fato, a propriedade de uma string binária com apenas zeros (e nenhum um) pode ser facilmente provada como não decidível por um algoritmo de tempo sublinear (não aproximado). Algoritmos de tempo sublinear surgem naturalmente na investigação de testes de propriedades .

Tempo linear

Diz-se que um algoritmo leva tempo linear , outempo, se sua complexidade de tempo for. Informalmente, isso significa que o tempo de execução aumenta no máximo linearmente com o tamanho da entrada. Mais precisamente, isso significa que existe uma constante c tal que o tempo de execução é no máximopara cada entrada de tamanho n . Por exemplo, um procedimento que soma todos os elementos de uma lista requer tempo proporcional ao comprimento da lista, se o tempo de adição for constante ou, pelo menos, limitado por uma constante.

O tempo linear é a melhor complexidade de tempo possível em situações em que o algoritmo precisa ler sequencialmente toda a entrada. Portanto, muita pesquisa tem sido investida na descoberta de algoritmos que exibem tempo linear ou, pelo menos, tempo quase linear. Esta pesquisa inclui métodos de software e hardware. Existem várias tecnologias de hardware que exploram o paralelismo para fornecer isso. Um exemplo é a memória endereçável por conteúdo . Esse conceito de tempo linear é usado em algoritmos de correspondência de strings, como o algoritmo de Boyer-Moore e o algoritmo de Ukkonen .

Tempo quase linear

Diz-se que um algoritmo é executado em tempo quase linear (também conhecido como tempo log-linear ) separa alguma constante positiva k ; [9] tempo linearítmico é o caso. [10] Usando a notação O suave, esses algoritmos são. Algoritmos de tempo quasilinear também sãopara cada constantee, portanto, executar mais rápido do que qualquer algoritmo de tempo polinomial cujo limite de tempo inclui um termopara qualquer.

Algoritmos que são executados em tempo quase linear incluem:

  • Classificação de mesclagem no local ,
  • Quicksort ,, em sua versão randomizada, tem um tempo de execução que éna expectativa na entrada do pior caso. Sua versão não randomizada possui umtempo de execução apenas ao considerar a complexidade média do caso.
  • Heapsort ,, merge sort , introsort , binary tree sort, smoothsort , paciência sorting , etc. na pior das hipóteses
  • Transformadas rápidas de Fourier ,
  • cálculo de matriz de Monge ,

Em muitos casos, otempo de execução é simplesmente o resultado da execução de umoperação n vezes (para a notação, veja Big O notation § Family of Bachmann–Landau notations ). Por exemplo, a classificação de árvore binária cria uma árvore binária inserindo cada elemento da matriz de tamanho n um por um. Como a operação de inserção em uma árvore de busca binária auto-balanceada levatempo, todo o algoritmo levaTempo.

As ordenações de comparação requerem pelo menoscomparações no pior caso, porque, pela aproximação de Stirling . Eles também surgem frequentemente da relação de recorrência .

Tempo subquadrático

Um algoritmo é chamado de tempo subquadrático se.

Por exemplo, algoritmos de ordenação simples, baseados em comparação, são quadráticos (por exemplo , ordenação por inserção ), mas podem ser encontrados algoritmos mais avançados que são subquadráticos (por exemplo , ordenação por shell ). Nenhuma ordenação de propósito geral é executada em tempo linear, mas a mudança de quadrático para subquadrático é de grande importância prática.

Tempo polinomial

Diz-se que um algoritmo é de tempo polinomial se seu tempo de execução é limitado superiormente por uma expressão polinomial no tamanho da entrada para o algoritmo, ou seja, T ( n ) = O ( n k ) para alguma constante positiva k . [1] [11] Problemas para os quais existe um algoritmo determinístico de tempo polinomial pertencem à classe de complexidade P , que é central no campo da teoria da complexidade computacional . tese de Cobhamafirma que o tempo polinomial é sinônimo de "tratável", "viável", "eficiente" ou "rápido". [12]

Alguns exemplos de algoritmos de tempo polinomial:

  • O algoritmo de ordenação de ordenação por seleção em n inteiros executaoperações para alguma constante A . Assim corre no tempoe é um algoritmo de tempo polinomial.
  • Todas as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) podem ser feitas em tempo polinomial.
  • As correspondências máximas em gráficos podem ser encontradas em tempo polinomial.

Tempo polinomial forte e fraco

Em alguns contextos, especialmente em otimização , diferencia-se entre algoritmos de tempo fortemente polinomial e de tempo fracamente polinomial . Esses dois conceitos só são relevantes se as entradas dos algoritmos consistirem em números inteiros.

O tempo fortemente polinomial é definido no modelo aritmético de computação. Neste modelo de computação, as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) levam um passo de unidade de tempo para serem executadas, independentemente do tamanho dos operandos. O algoritmo é executado em tempo fortemente polinomial se: [13]

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

Qualquer algoritmo com essas duas propriedades pode ser convertido em 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 . A segunda condição é estritamente necessária: dado o inteiro(que ocupa espaço proporcional a n no modelo de máquina de Turing), é possível calcularcom n multiplicações usando quadrados repetidos . No entanto, o espaço utilizado para representaré proporcional a, e, portanto, exponencial em vez de polinômio no espaço usado para representar a entrada. Portanto, não é possível realizar esse cálculo em tempo polinomial em uma máquina de Turing, mas é possível calculá-lo polinomialmente por muitas operações aritméticas.

No entanto, para a primeira condição, existem algoritmos que são executados em várias etapas da máquina de Turing limitadas por um polinômio no comprimento da entrada codificada em binário, mas não realizam várias operações aritméticas limitadas por um polinômio no número de entrada números. O algoritmo euclidiano para calcular o máximo divisor comum de dois inteiros é um exemplo. Dados dois inteirose, o algoritmo executaoperações aritméticas em números com no máximobits. Ao mesmo tempo, o número de operações aritméticas não pode ser limitado pelo número de inteiros na entrada (que é constante neste caso, há sempre apenas dois inteiros na entrada). Devido a esta última observação, o algoritmo não é executado em tempo fortemente polinomial. Seu tempo real de execução depende logaritmicamente das magnitudes dee(ou seja, em seu comprimento em bits) e não apenas no número de inteiros na entrada.

Diz-se que um algoritmo que é executado em tempo polinomial, mas que não é fortemente polinomial, é executado em tempo fracamente polinomial . [14] Um exemplo bem conhecido de um problema para o qual um algoritmo de tempo polinomial fraco é conhecido, mas não é conhecido por admitir um algoritmo de tempo polinomial forte, é a programação linear . O tempo polinomial fraco não deve ser confundido com o tempo pseudo-polinomial , que depende linearmente da magnitude dos valores no problema e não é um tempo verdadeiramente 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 o tempo polinomial são as seguintes.

P é a menor classe de complexidade de tempo em uma máquina determinística que é robusta em termos de mudanças no modelo de máquina. (Por exemplo, uma mudança de uma máquina de Turing de fita única para uma máquina de múltiplas fitas pode levar a uma aceleração quadrática, mas qualquer algoritmo que seja executado em tempo polinomial em um modelo também o fará no outro.) Qualquer máquina abstrata fornecerá tem uma classe de complexidade correspondente aos problemas que podem ser resolvidos em tempo polinomial nessa máquina.

Tempo superpolinomial

Um algoritmo é definido para tomar tempo superpolinomial se T ( n ) não for limitado acima por nenhum polinômio. Usando pouca notação ômega , é ω ( nc ) tempo para todas as constantes c , onde n é o parâmetro de entrada, normalmente o número de bits na entrada.

Por exemplo, um algoritmo executado por 2 n passos em uma entrada de tamanho n requer tempo superpolinomial (mais especificamente, tempo exponencial).

Um algoritmo que usa recursos exponenciais é claramente superpolinomial, mas alguns algoritmos são apenas fracamente superpolinomiais. Por exemplo, o teste de primalidade Adleman–Pomerance–Rumely é executado por n O (log log n ) tempo em entradas de n bits; isso cresce mais rápido do que qualquer polinômio para n grande o suficiente , mas o tamanho da entrada deve se tornar impraticavelmente grande antes que não possa ser dominado por um polinômio com grau pequeno.

Um algoritmo que requer tempo superpolinomial está fora da classe de complexidade P . A tese de Cobham postula que esses algoritmos são impraticáveis ​​e, em muitos casos, são. Como o problema P versus NP não está resolvido, não se sabe se problemas NP-completos requerem tempo superpolinomial.

Tempo quase polinomial

Os algoritmos de tempo quase polinomial são algoritmos que executam mais do que o tempo polinomial, mas não tão longos quanto o tempo exponencial. O pior caso de tempo de execução de um algoritmo de tempo quase polinomial épara alguns fixo. Porobtemos um algoritmo de tempo polinomial, paraobtemos um algoritmo de tempo sublinear.

Algoritmos de tempo quase polinomial geralmente surgem em reduções de um problema NP-difícil para outro problema. Por exemplo, pode-se pegar uma instância de um problema NP difícil, digamos 3SAT , e convertê-la em uma instância de outro problema B, mas o tamanho da instância se torna. Nesse caso, esta redução não prova que o problema B é NP-difícil; essa redução mostra apenas que não há algoritmo de tempo polinomial para B, a menos que haja um algoritmo de tempo quase polinomial para 3SAT (e, portanto, todo NP ). Da mesma forma, existem alguns problemas para os quais conhecemos algoritmos de tempo quase polinomial, mas nenhum algoritmo de tempo polinomial é conhecido. Tais problemas surgem em algoritmos de aproximação; um exemplo famoso é o problema da árvore de Steiner dirigido , para o qual existe um algoritmo de aproximação de tempo quase polinomial que alcança um fator de aproximação de( n sendo o número de vértices), mas mostrar a existência de tal algoritmo de tempo polinomial é um problema em aberto.

Outros problemas computacionais com soluções de tempo quase polinomial, mas nenhuma solução de tempo polinomial conhecida, incluem o problema de clique plantado no qual o objetivo é encontrar um clique grande na união de um clique e um grafo aleatório . Embora quase polinomialmente solucionável, foi conjecturado que o problema do clique plantado não tem solução em tempo polinomial; essa conjectura de clique plantado tem sido usada como uma suposição de dureza computacional para provar a dificuldade de vários outros problemas em teoria computacional de jogos , teste de propriedades e aprendizado de máquina . [15]

A classe de complexidade QP consiste em todos os problemas que possuem algoritmos de tempo quase polinomial. Ele pode ser definido em termos de DTIME da seguinte forma. [16]

Relação com problemas NP-completos

Na teoria da complexidade, o problema P versus NP não resolvido pergunta se todos os problemas em NP têm algoritmos de tempo polinomial. Todos os algoritmos mais conhecidos para problemas NP-completos como 3SAT etc. levam tempo exponencial. De fato, é conjecturado para muitos problemas NP-completos naturais que eles não possuem algoritmos de tempo subexponencial. Aqui "tempo subexponencial" é entendido como a segunda definição apresentada abaixo. (Por outro lado, muitos problemas de grafos representados de maneira natural por matrizes de adjacência são solucionáveis ​​em tempo subexponencial simplesmente porque o tamanho da entrada é o quadrado do número de vértices.) Esta conjectura (para o problema k-SAT) é conhecida como a hipótese do tempo exponencial . [17]Uma vez que se conjectura que problemas NP-completos não possuem algoritmos de tempo quasi-polinomial, alguns resultados de inaproximação no campo de algoritmos de aproximação fazem a suposição de que problemas NP-completos não possuem algoritmos de tempo quasi-polinomial. Por exemplo, veja os resultados de inaproximabilidade conhecidos para o problema de cobertura do conjunto .

Tempo subexponencial

O termo tempo subexponencial é 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 um exponencial. Nesse sentido, problemas que possuem algoritmos de tempo subexponencial são um pouco mais tratáveis ​​do que aqueles que possuem apenas algoritmos exponenciais. A definição precisa de "subexponencial" não é geralmente aceita, [18] e listamos as duas mais amplamente utilizadas abaixo.

Primeira definição

Um problema é dito ser solucionável em tempo subexponencial se ele puder ser resolvido em tempos de execução cujos logaritmos crescem menores que qualquer polinômio dado. Mais precisamente, um problema está em tempo subexponencial 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 segue. [5] [19] [20] [21]

Esta noção de subexponencial é não uniforme em termos de ε no sentido de que ε não faz parte da entrada e cada ε pode ter seu próprio algoritmo para o problema.

Segunda definição

Alguns autores definem tempo subexponencial como tempos de execução em. [17] [22] [23] Esta definição permite tempos de execução maiores do que a primeira definição de tempo subexponencial. Um exemplo de tal algoritmo de tempo subexponencial é o algoritmo clássico mais conhecido para fatoração de inteiros, a peneira de campo de número geral , que é executada no tempo aproximadamente, onde o comprimento da entrada é n . Outro exemplo foi o problema do isomorfismo de grafos , que o algoritmo mais conhecido de 1982 a 2016 resolveu em. No entanto, no STOC 2016 foi apresentado um algoritmo de tempo quase polinomial. [24]

Faz diferença se o algoritmo pode ser subexponencial no tamanho da instância, no número de vértices ou no número de arestas. Na complexidade parametrizada , essa diferença é explicitada considerando os pares .de problemas de decisão e parâmetros k . SUBEPT é a classe de todos os problemas parametrizados que rodam em tempo subexponencial em k e polinomial no tamanho de entrada n : [25]

Mais precisamente, SUBEPT é a classe de todos os problemas parametrizadospara o qual existe uma função computável come um algoritmo que decide L no tempo.

Hipótese de tempo exponencial

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

Tempo exponencial

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

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

Tempo fatorial

Diz-se que um algoritmo é tempo fatorial se T(n) é limitado superiormente pela função fatorial n! . O tempo fatorial é um subconjunto do tempo exponencial (EXP) porquepara todos. No entanto, não é um subconjunto de E.

Um exemplo de algoritmo executado em tempo fatorial é o bogosort , um algoritmo de ordenação notoriamente ineficiente baseado em tentativa e erro . O Bogosort classifica uma lista de n itens embaralhando repetidamente a lista até que ela seja classificada. No caso médio, cada passagem pelo algoritmo bogosort examinará um dos n ! ordenações dos n itens. Se os itens forem distintos, apenas uma dessas ordenações será classificada. Bogosort compartilha patrimônio com o teorema do macaco infinito .

Tempo exponencial duplo

Diz-se que um algoritmo tem tempo exponencial duplo se T ( n ) é limitado superiormente por 2 2 poly( n ) , onde poly( n ) é algum polinômio em n . Tais algoritmos pertencem à classe de complexidade 2-EXPTIME .

Algoritmos de tempo exponencial duplo bem conhecidos incluem:

Veja também

Referências

  1. ^ a b Sipser, Michael (2006). Introdução à Teoria da Computação . Curso Tecnologia Inc. ISBN 0-619-21764-2.
  2. ^ Mehlhorn, Kurt ; Naher, Stefan (1990). "Dicionários ordenados limitados em tempo O (log log N ) e espaço O ( n ) ". Cartas de Processamento de Informações . 35 (4): 183–189. doi : 10.1016/0020-0190(90)90022-P .
  3. ^ Tao, Terence (2010). "1.11 O teste de primalidade AKS" . Um epsilon of room, II: Páginas do terceiro ano de um blog de matemática . Pós-Graduação em Matemática. Vol. 117. Providence, RI: American Mathematical Society. págs. 82-86. doi : 10,1090/gsm/117 . ISBN 978-0-8218-5280-4. MR  2780010 .
  4. ^ Lenstra, HW Jr .; Pomerance, Carl (2019). "Teste de primalidade com períodos gaussianos" (PDF) . Jornal da Sociedade Europeia de Matemática . 21 (4): 1229-1269. doi : 10.4171/JEMS/861 . MR 3941463 . S2CID 127807021 .   
  5. ^ a b Babai, László ; Fortnow, Lance ; Nisan, N .; Wigderson, Avi (1993). "BPP tem simulações de tempo subexponencial a menos que EXPTIME tenha provas publicáveis". Complexidade Computacional . Berlim, Nova York: Springer-Verlag . 3 (4): 307-318. doi : 10.1007/BF01275486 . S2CID 14802332 . 
  6. ^ Bradford, Phillip G.; Rawlins, Gregory JE; Shannon, Gregory E. (1998). "Ordenação eficiente da cadeia de matrizes em tempo de polílogo". SIAM Journal on Computing . 27 (2): 466–490. doi : 10.1137/S0097539794270698 . MR 1616556 . 
  7. ^ Holm, Jacob; Rotenberg, Eva (2020). "Teste de planaridade totalmente dinâmico em tempo polilogarítmico". Em Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). Anais do 52º Simpósio Anual ACM SIGACT sobre Teoria da Computação, STOC 2020, Chicago, IL, EUA, 22 a 26 de junho de 2020 . Associação de Máquinas de Computação. págs. 167-180. arXiv : 1911.03449 . doi : 10.1145/3357713.3384249 .
  8. ^ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Algoritmos de tempo sublinear" (PDF) . Notícias SIGACT . 34 (4): 57–67. doi : 10.1145/954092.954103 . S2CID 65359 .  
  9. ^ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "Na teoria da complexidade de tempo quase linear" (PDF) . Informática Teórica . 148 (2): 325–349. doi : 10.1016/0304-3975(95)00031-Q . MR 1355592 .  
  10. ^ Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4ª ed.). Pearson Educação. pág. 186.
  11. ^ Papadimitriou, Christos H. (1994). Complexidade computacional . Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
  12. ^ Cobham, Alan (1965). "A dificuldade computacional intrínseca de funções". Proc. Lógica, Metodologia e Filosofia da Ciência II . Holanda do Norte.
  13. ^ Grötschel, Martin ; László Lovász ; Alexander Schrijver (1988). "Complexidade, Oráculos e Computação Numérica". Algoritmos Geométricos e Otimização Combinatória . Springer. ISBN 0-387-13624-X.
  14. ^ Schrijver, Alexander (2003). "Preliminares sobre algoritmos e complexidade". Otimização Combinatória: Poliedros e Eficiência . Vol. 1. Springer. ISBN 3-540-44389-4.
  15. ^ Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omni (2017). "Dureza ETH para subgrafo k mais denso com perfeição perfeita". Em Klein, Philip N. (ed.). Anais do Vigésimo Oitavo Simpósio Anual ACM-SIAM sobre Algoritmos Discretos, SODA 2017, Barcelona, ​​Espanha, Hotel Porta Fira, 16 a 19 de janeiro . Sociedade de Matemática Industrial e Aplicada. págs. 1326-1341. arXiv : 1504.08352 . doi : 10.1137/1.9781611974782.86 . MR 3627815 . 
  16. ^ Complexidade Zoo : Classe QP: Tempo Quasipolinomial
  17. ^ a b Impagliazzo, Russell ; Paturi, Ramamohan (2001). "Sobre a complexidade do k -SAT" (PDF) . Revista de Ciências da Computação e Sistemas . 62 (2): 367–375. doi : 10.1006/jcss.2000.1727 . MR 1820597 .  
  18. Aaronson, Scott (5 de abril de 2009). "Um dilema não muito exponencial" . Otimizado para Shtetl . Recuperado em 2 de dezembro de 2009 .
  19. ^ Complexidade Zoo : Classe SUBEXP: Deterministic Subexponencial-Time
  20. ^ Moser, P. (2003). "Categorias de Baire em classes de pequena complexidade". Em Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentos da Teoria da Computação: 14º Simpósio Internacional, FCT 2003, Malmö, Suécia, 12 a 15 de agosto de 2003, Anais . Notas de aula em Ciência da Computação . Vol. 2751. Berlim, Nova York: Springer-Verlag. pp. 333-342. doi : 10.1007/978-3-540-45077-1_31 . ISBN 978-3-540-40543-6. ISSN  0302-9743 .
  21. ^ Miltersen, PB (2001). "Desrandomizando Classes de Complexidade". Manual de Computação Randomizada . Otimização Combinatória. Kluwer Academic Pub. 9 : 843. doi : 10.1007/978-1-4615-0013-1_19 . ISBN 978-1-4613-4886-3.
  22. ^ Kuperberg, Greg (2005). "Um algoritmo quântico de tempo subexponencial para o problema de subgrupo oculto diedro". SIAM Journal on Computing . Filadélfia. 35 (1): 188. arXiv : quant-ph/0302112 . doi : 10.1137/s0097539703436345 . ISSN 1095-7111 . S2CID 15965140 .  
  23. ^ Oded Regev (2004). "Um Algoritmo de Tempo Subexponencial para o Problema de Subgrupo Diédrico Oculto com Espaço Polinomial". arXiv : quant-ph/0406151v1 .
  24. ^ Grohe, Martin; Neuen, Daniel (2021). "Avanços recentes sobre o problema de isomorfismo de grafos". arXiv : 2011.01366 . {{cite journal}}:Cite journal requer |journal=( ajuda )
  25. ^ Flum, Jörg; Grohe, Martin (2006). Teoria da Complexidade Parametrizada . Springer. pág. 417. ISBN 978-3-540-29952-3.
  26. ^ Impagliazzo, R. ; Paturi, R.; Zane, F. (2001). "Quais problemas têm complexidade fortemente exponencial?" . Revista de Ciências da Computação e Sistemas . 63 (4): 512-530. doi : 10.1006/jcss.2001.1774 .
  27. ^ Mayr, Ernst W .; Meyer, Albert R. (1982). "A complexidade dos problemas de palavras para semigrupos comutativos e ideais polinomiais" . Avanços em Matemática . 46 (3): 305–329. doi : 10.1016/0001-8708(82)90048-2 . MR 0683204 . 
  28. ^ Davenport, James H. ; Heintz, Joos (1988). "A eliminação do quantificador real é duplamente exponencial" . Revista de Computação Simbólica . 5 (1–2): 29–35. doi : 10.1016/S0747-7171(88)80004-X . MR 0949111 . 
  29. ^ Collins, George E. (1975). "Eliminação do quantificador para campos fechados reais por decomposição algébrica cilíndrica". Em Brakhage, H. (ed.). Teoria dos Autômatos e Linguagens Formais: 2ª Conferência GI, Kaiserslautern, 20-23 de maio de 1975 . Notas de aula em Ciência da Computação. Vol. 33. Springer. págs. 134-183. doi : 10.1007/3-540-07407-4_17 . MR 0403962 .