Quais são as consequências de fatorar o NP-completo?

Respostas:

26

Além de implicar NP = co-NP, também implicaria que o BQP continha NP.

Também parece implicar que instâncias difíceis de problemas completos de NP foram fáceis de gerar.

Joe Fitzsimons
fonte
21

Como a fatoração de número inteiro é conhecida como NP e co-NP , uma prova de que é NP- completo implicaria NP = co-NP , o que é considerado altamente improvável.

Há uma discussão interessante neste post antigo de Lance Fortnow .

Daniel Apon
fonte