Mostrar que não pode existir um algoritmo (determinista, em um computador clássico) para fatorar um inteiro x, com tempo de execução polinomial em log 2 x (Ou produzir o algoritmo).

Passo 1

O enunciado pede para mostrar que não pode existir um algoritmo determinista clássico que, dado um inteiro x, produza sua fatoração em tempo polinomial em log2x. Alternativamente, pede para apresentar tal algoritmo. O conteúdo envolve complexidade computacional e, em particular, a colocação do problema de fatoração na classe P.

Passo 2

Vamos expor a situação atual em teoria da complexidade:
  1. Definimos o tamanho da entrada como n = lceil log2xrceil, pois precisamos de n bits para escrever x.
  2. Um algoritmo em tempo polinomial em log2x seria, em outras palavras, um algoritmo em tempo poly(n), ou seja, pertencente à classe P.
  3. Sabe-se que o problema de fatorar um inteiro está em NPcap coNP (na prática, em NP e também tem certificados de não-fatoração), e existe o algoritmo quântico de Shor que o resolve em tempo polinomial quântico, mas NÃO se conhece nenhum algoritmo determinista clássico em tempo poly(n).

Passo 3

Como não há, até o momento, nenhuma prova de que Pneq NP nem de que fatores não podem ser obtidos em tempo polinomial clássico, tampouco há um algoritmo eficiente conhecido, o status do problema de fatoração em P é simplesmente um problema em aberto na teoria da complexidade. Portanto, não podemos:
  • Provar (hoje) que não existe algoritmo determinista polinomial para fatorar;
  • Nem apresentar (hoje) um algoritmo que o faça.

Resposta

O problema de fatoração de inteiros em tempo polinomial clássico é atualmente um problema em aberto em teoria da complexidade. Não se sabe provar que não existe tal algoritmo, nem foi encontrado um algoritmo determinista clássico que realize a fatoração em tempo poly(log2x).

Exercícios de Livros Relacionados