Pergunta

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM whose longest computational branch runs in polynomial time. The TM will do the following: Given an input (binary) word w of length n on the tape: Non deterministically guess i factors, 1<=i<=n, such that each of the factors is a binary string no longer than n. Multiply all of the factors together (I think this should take O(n^3)) and accept if the final number on the tape is equal to w. Otherwise, reject.

Am I missing anything?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top