Prove that the problem of factoring α is in NP

Question

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 α.

Answer 1

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.

Answer 2

Problem in P : is a problem, that is computable by Deterministic Turing Machine in polynomial time Problem in NP : is a problem, thas is polynomicaly veryfiable by Deterministic Turing Machine.

In NP, we are using non-determinism in such way, that we require only one branch of a computation tree to be accepted (we try "all" possibilities at the "same" time). Polynomicaly veryfiable means, that we have a certificate (let it be c), that is a solution to the input word (let it be w). Certificate must be of a polynomial length considering input length. Our task is only to verify if a certificate is a solution. For example in SAT(satisfyability problem) a certificate is a correct assignement (which is guessed non-deterministically).

So You prove that your problem is in NP : There exists a DTM that verifies a pair (w,c), where w is input number and c are its factors. You must just construct a veryfier that multiplies factors in c and compares it to w.