Tip:
Highlight text to annotate it
X
Estamos enviando nossas tropas para as fronteiras do leste.
Infelizmente, depois das chuvas pesadas
os tanques atolaram na lama.
Temos que construir uma enorme malha rodoviária
que conecte todos os pontos estratégicos.
Não podemos bancar isso. Ela tem que ser o menor possível.
Professor...
Steiner...
Árvore de Steiner é um problema NP-completo.
Ele não pode ser resolvido em tempo polinomial.
Graduandos, saiam.
Doutores Keitel, Jodel, Krebs e Bogdan fiquem aqui.
Isso é ultrajante.
Não pode ser resolvido em tempo polinomial?
Isso é idiotice. Vocês provaram que P != NP?
Vocês se fizeram de idiotas na frente dos graduandos.
O que eu ensinei pra vocês?
NP-completo não significa exponencial, até os idiotas da SS sabem disso.
Com essa falta de compreensão
é um milagre que vocês passaram no exame teórico de Algoritmos.
Professor, ninguém pode resolver problemas NP-completos em tempo polinomial.
O quê? Você já ouviu falar em aproximação?
Professor, isso não vai ajudar.
Você sabia que o Terceiro Reich é um espaço euclidiano?
Você pode computar árvores de Steiner
com uma aproximação arbitrariamente boa
e o expoente nem mesmo depende do epsilon.
Você atribui epsilon=0.001 e está feito.
Mas o que vocês sabem sobre o algoritmo do Arora
se vocês nem mesmo sabem o que um PTAS é.
Vocês lêem uma redução boba
e pensam que não podem fazer nada.
Eu não posso contar com vocês.
Farei eu mesmo! Eu implementarei a solução.
A Europa inteira verá como os Nazistas podem programar!
Um par de heurísticas
e irá funcionar perfeitamente.
Vocês provavelmente escreveriam o Dijkstra em tempo exponencial!
Para vocês isso é uma diferença pequena.
Vocês não têm ideia dos avanços modernos.
Vocês nem mesmo sabem algoritmos básicos de aproximação.
Se acalme, eu explicarei pra você um PTAS para o problema da mochila.
Droga! Eu esqueci de uma coisa.
O artigo do Arora está no Springer
e nós não fizemos a assinatura.
Acabou, nós não podemos implementar isso.
Nós teremos que fazer uma 2-aproximação.
Ao invés, nós computaremos
uma árvore geradora mínima.