Quais são alguns problemas não triviais em que sabemos que o algoritmo atual que temos é o ideal assintoticamente ideal? (Para máquinas de turing)
E como isso é provado?
Quais são alguns problemas não triviais em que sabemos que o algoritmo atual que temos é o ideal assintoticamente ideal? (Para máquinas de turing)
E como isso é provado?
Respostas:
Qualquer algoritmo que leva tempo linear e precisa ler toda a sua entrada deve ser assintoticamente ideal. Da mesma forma, como comenta Raphael, qualquer algoritmo cujo tempo de execução seja da mesma ordem que o tamanho da saída é ideal.
fonte
Se a medida de complexidade que você está considerando é a complexidade da consulta, ou seja, o número de vezes que a máquina precisa examinar a entrada para resolver um problema específico, existem muitos problemas para os quais temos algoritmos ideais. A razão para isso é que limites mais baixos para a complexidade da consulta são mais fáceis de alcançar do que limites mais baixos para a complexidade do tempo ou espaço, graças a algumas técnicas populares, incluindo o método adversário .
A desvantagem, no entanto, é que essa medida de complexidade é quase excessivamente usada no processamento de informações quânticas, pois fornece uma maneira fácil de provar uma lacuna entre o poder computacional clássico e quântico. O algoritmo quântico mais notório nessa estrutura é o algoritmo de Grover . Dada uma sequência binária para a qual existe um único tal que , você deve encontrar . Classicamente (sem um computador quântico), o algoritmo mais trivial é ideal: você precisa consultar essa sequência vezes, em média, para encontrar . Grover forneceu um algoritmo quântico que o faz emx1,…,xn i xi=n i n/2 i O(n−−√) consultas para a string. Isso também se mostrou ótimo.
fonte
fonte
A classificação por comparação usando comparações (classificação por mesclagem, para citar um) é ideal; a prova envolve simplesmente o cálculo da altura de uma árvore com n ! folhas.O(nlogn) n!
Supondo que a Unique Games Conjecture, Khot, Kindler, Mossel e O'donnell mostraram que é NP-completo aproximar o Max-Cut melhor do que o algoritmo de Goemans e Williamson. Portanto, nesse sentido, G&W é ideal (assumindo também que ).P≠NP
Alguns algoritmos distribuídos podem ser ótimos em relação a algumas condições (por exemplo, a proporção de processadores adversários), mas desde que você mencionou as máquinas de Turing, acho que esse não é o tipo de exemplo que você está procurando.
fonte
Suponha que você está dado entrada e pede para decidir se a máquina RAM M termina na entrada x depois de t passos. Pelo teorema da hierarquia temporal, o algoritmo ideal para decidir isso é simular a execução de M ( x ) para etapas t , o que pode ser feito no tempo O ( t ) .w=⟨M,x,t⟩ M x t M(x) t O(t)
(Nota: para máquinas de Turing, a simulação da execução de executa etapas O ( t log t ) ; sabemos apenas um limite inferior de Ω ( t ) . Portanto, isso não é ideal para as máquinas de Turing especificamente).M O(tlogt) Ω(t)
Existem outros problemas que contêm a versão do problema de interrupção como um sub-caso. Por exemplo, decidir se uma sentença é uma conseqüência do WS1S leva tempo 2 ↑ ↑ O ( | θ | ) e isso é ideal.θ 2↑↑O(|θ|)
fonte
Não sei ao certo o que você quer dizer com "não trivial", mas e quanto a isso? . Portanto, esse idioma não é regular, qualquer TM que decide que deve executar em Ω ( n log n ) . O algoritmo simples (cruzando todos os outros 0) é ideal.L={02k|k≥0} Ω(nlogn)
fonte
Se você permitir problemas dinâmicos na estrutura de dados, conheceremos algoritmos ótimos de tempo super-lineares. Isso está no modelo de sonda de célula, que é tão forte quanto a palavra RAM, ou seja, este não é um modelo restrito, como árvores de decisão algébricas.
Um exemplo é manter as somas de prefixo sob atualizações dinâmicas. Começamos com uma matriz de números , e o objetivo é manter uma estrutura de dados que permita as seguintes operações:A[1],…,A[n]
Você pode suportar facilmente as duas operações em tempo com uma estrutura de dados baseada em uma árvore binária aumentada com A [ i ] nas folhas. Patrascu e Demaine mostraram que isso é ótimo: para qualquer estrutura de dados, há uma sequência de n adições e consultas de soma de prefixos que devem levar Ω ( n log n ) tempo total.O(logn) A[i] n Ω(nlogn)
fonte
Muitos algoritmos de streaming têm limites superiores que correspondem aos limites inferiores.
fonte
existem dois algoritmos de busca um tanto semelhantes que [meu entendimento é] são ótimos com base em restrições específicas na ordem / distribuição de entrada. no entanto, as apresentações dos algoritmos normalmente não enfatizam essa otimização.
a seção áurea busca encontrar o máximo ou o mínimo (extremo) de uma função unimodal. assume que a entrada é uma função unimodal. encontra-o em tempo logarítmico, em média. pelo que me lembro, pode ter havido uma prova de otimalidade no livro Estrutura e Interpretação de Programas de Computador por Abelson & Sussman.
a pesquisa binária encontra um ponto no tempo logarítmico, em média, em uma lista classificada, mas requer que a entrada seja classificada.
estou citando a Wikipedia acima, mas ela não tem as provas de que elas são ótimas, talvez outras referências que provam a otimização possam ser encontradas pelo público.
fonte
Muitos algoritmos de tempo sublinear têm limites superiores que correspondem aos limites inferiores.
fonte