Quais são alguns problemas em que sabemos que temos um algoritmo ideal?

15

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?

sture
fonte
11
Uma máquina de turing é um modelo complicado para limites mais baixos. Alterar o defn pode alterar o polinômio no tempo de execução, portanto, você precisa ser um pouco mais específico.
Suresh Venkat
Como você define não trivial?
Funkstar
1
Como diz Suresh, o tipo de MT que você usa tem influência. Eu acho que para o idioma dos palíndromos (palavras que você pode ler para trás), temos uma TM de 1 fita ideal que O(n2) etapas para decidir o idioma. E para as TMs de 2 fitas, é decidível em tempo linear, portanto, também é ideal.
27612 Bruno Bruno
Veja também mathoverflow.net/questions/31448/…
BlueRaja - Danny Pflughoeft

Respostas:

18

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.

Máx.
fonte
10
Da mesma forma, qualquer algoritmo cujo tempo de execução seja da mesma ordem que o tamanho da saída é ideal.
Raphael
9
Acredito que essa resposta e o comentário a seguir sejam o estado da arte completo.
Jeffε
9
Bem, isso foi decepcionante
sture
1
Para constar, o comentário de Jɛ ff E parece se referir à resposta de Shir abaixo.
András Salamon
1
Eu estava me referindo à resposta de Max, não à de Shir, e ao comentário de Raphael sobre a resposta de Max.
Jeffε
8

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,,xnixi=nin/2iO(n)consultas para a string. Isso também se mostrou ótimo.

Philippe Lamontagne
fonte
2
De fato, a complexidade da consulta é a base subjacente da resposta de Max. Para a maioria dos problemas, qualquer algoritmo "provavelmente tem que ler toda a entrada" ou pelo menos uma fração constante da entrada.
Jeffε
6
  • Se você estiver disposto a alterar seu modelo, há limites muito baixos nas estruturas de dados. Consulte Limites inferiores para estruturas de dados para obter referências sobre boas referências para limites inferiores nas estruturas de dados.
  • No limite de para classificação no modelo de comparação que algumas pessoas mencionaram aqui, você pode obter um limite semelhante para o problema do casco convexo, considerando o caso em que a entrada é composta de pontos ao longo do gráfico de uma função crescente no primeiro quadrante do plano.Ω(nlogn)
Abel Molina
fonte
2
+1 por mencionar estruturas de dados. Mas não creio que seja possível obter um limite inferior útil para cascos convexos por meio dos limites inferiores de comparação para classificação. A razão é que o modelo de comparação não é poderoso o suficiente para calcular cascos convexos. O que funciona é usar um modelo mais poderoso, como árvores de decisão algébricas nas quais os cascos podem ser computados e, em seguida, adaptar o limite inferior da classificação a esse modelo mais poderoso.
David Eppstein
Faz sentido, obrigado pelo esclarecimento!
Abel Molina
3
  1. 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!

  2. 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 ).PNP

  3. 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.

Shir
fonte
2
Se o item 2 responde ou não à pergunta depende do que o solicitante quer dizer com “ideal”, embora eu duvide que o solicitante esteja perguntando nesse sentido (caso contrário, existem muitos, muitos resultados de aproximações apertados que nem exigem UGC). Além disso, não acho que o item 1 ou 3 responda à pergunta.
Tsuyoshi Ito 21/01
@TsuyoshiIto, é difícil adivinhar o que exatamente o autor da pergunta quis dizer, e foi isso que me fez tentar respostas em várias direções, na esperança de encontrar algo útil para ele. O que faz você dizer que (1) não é uma resposta válida, a propósito?
Shir
2
O solicitante solicita especificamente um algoritmo ideal para a máquina de Turing .
Tsuyoshi Ito 21/01
6
A "classificação por comparação" é realmente um "problema"? Ou é um problema e uma restrição no modelo de computação?
Jeffε
3

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,tMxtM(x)tO(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).MO(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(|θ|)

David Harris
fonte
3

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|k0}Ω(nlogn)

aelguindy
fonte
3

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]

  • Adicione a A [ i ] , dados i e ΔΔA[i]iΔ
  • Calcule a soma do prefixo , dado ij=1iA[i]i

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)

{1,n}

  • ijij
  • ii

O(α(n))αnΩ(nα(n))

Sasho Nikolov
fonte
1

Muitos algoritmos de streaming têm limites superiores que correspondem aos limites inferiores.

Bin Fu
fonte
0

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.

vzn
fonte
-1

Muitos algoritmos de tempo sublinear têm limites superiores que correspondem aos limites inferiores.

Bin Fu
fonte
3
Sinalizado como duplicado.
Jeffε
Algoritmo sublinhado de tempo e algoritmo de streaming são áreas diferentes.
Bin Fu
1
Isso é verdade, mas você deve combinar as respostas em uma.
precisa saber é o seguinte
Alguns exemplos de algoritmos de tempo sublinear ideais podem ser
Bin Fu
1
também não está claro por que isso não é uma duplicata da resposta da complexidade da consulta.
Artem Kaznatcheev