Exemplo de complexidade polinomial

Em relação a post anterior, sobre complexidade pseudo-polinomial (vide https://informacaoquantica.wordpress.com/2020/08/27/por-que-a-complexidade-computacional-da-fatoracao-de-numeros-inteiros-e-expraizn/), surgiu a pergunta sobre um exemplo de algoritmo puramente polinomial (ou seja, que o tamanho da entrada não importa). É uma pergunta interessante, porque, bem ou mal, uma entrada com tamanho gigante (digamos, 10020134321423423040055096699699696909) sempre vai pesar no algoritmo. Bom, um exemplo simples é o …

Continue lendo Exemplo de complexidade polinomial

Por que a complexidade computacional da fatoração de números inteiros é exp(raiz(N))?

Fatorar um número inteiro significa encontrar os fatores primos deste. Exemplos: 15 = 3*5, ou 187 = 11*17 A fatoração tem duas características: é difícil de fazer, mas é fácil de checar se uma solução é válida. Exemplo: Quais os fatores primos de 3127? Um método possível para encontrar os fatores do número N é …

Continue lendo Por que a complexidade computacional da fatoração de números inteiros é exp(raiz(N))?