Please enable JavaScript.

Coggle requires JavaScript to display documents.

Limites da Computação - Coggle Diagram

- - - - Conhecemos algoritmos não determinísticos eficientes, mas não sabemos se existem algoritmos determinísticos eficientes para eles. Ao mesmo tempo, não foi capaz de provar que nenhum desses problemas não possui algoritmos determinísticos eficientes. Essa classe de problemas é chamada de NP-completo. Se alguém encontrar a solução para qualquer um deles que rode em tempo polinomial em um computador comum, então por uma série de reduções, todos os outros problemas que estão em NP também podem ser resolvidos em tempo polinomial em um computador comum!
  - - - Por exemplo, o problema do CAIXEIRO VIAJANTE cresce tão rápido que para problemas muito além de 30 cidades, não pode ser executado em computadores modernos.
        
        Porém, outros problemas em NP, embora exijam tempo exponencial, crescem lento o suficiente para terem soluções para problemas de um tamanho útil.
        
        Há um algoritmo de programação dinâmica de custo Θ(nK) para n objetos sendo encaixados em uma mochila de tamanho K.Apesar disso, o Problema da Mochila é NP-completo. Ele é tratável se os números estiverem na casa dos milhares. Algoritmos assim são chamados de algoritmos de tempo pseudo-polynomial.