Search code examples
computation-theorynp

Prove that the problem of factoring α is in NP

Trying to brush up on computation theory but am not sure of solution to this:

Prove that the problem of factoring α is in NP.

I have a feeling it may be related to finding an NP problem and finding a reduction to the problem of factoring α.

Solution

  • This is simple actually. Multiplication is in P. NP is the same as "checking all possible polynomial sized solutions in parallel". If alpha is encoded as a length n bitstring, the factors total length is at most n + c.

    What it is not is "NP-complete". There is no way to turn an arbitrary NP problem into factoring.