Mostrar que não pode existir um algoritmo (determinista, em um computador clássico) para fatorar um inteiro
, com tempo de execução polinomial em
(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
, produza sua fatoração em tempo polinomial em
. 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
.
Passo 2
Vamos expor a situação atual em teoria da complexidade:
- Definimos o tamanho da entrada como
, pois precisamos de bits para escrever . - Um algoritmo em tempo polinomial em
seria, em outras palavras, um algoritmo em tempo , ou seja, pertencente à classe . - Sabe-se que o problema de fatorar um inteiro está em
(na prática, em 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 .
Passo 3
Como não há, até o momento, nenhuma prova de que
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
é 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
.