Say I have a number 45What are the factors of 45?1, 3, 5, 9, 15, 45Is there any other factors?I know that if I want to find some non trivial factor of some number, say 45, I know it's in NP.I can non deterministically choose some 2 numbers and verify that those 2 numbers are factors of my large number. Verifying is easy. Just multiply the 2 numbers and see if it match.What about if I want to find ALL factors of a large number? Is it still in NP?How do we verify, in polynomial time, that 1, 3, 15, 45 are all the factors of 45? It turns out it isn't because we still have 5 and 9. But say someone saysOkay, 1, 3, 15, 45 are all factors of 45. How do we verify it in polynomial time?Is it in NP?Is it NP complete?Does it has P verifier?Basically, I wonder if the following problems are in NPSay n is a numberSay S is a set of numbers between 1 and nIs S the set of ALL factors of n or not.A program should say it's false whenOne element of S, say s, is not a factor of n. We can verify this by dividing n by s and see if there are some reminders.There exist a number, say f, not in S, but is actually a factor of n.Now is that problem NP?
Is knowing ALL factors of a large number an NP?
np
NP is a class of decision problems. Only decision problems can belong to NP. The problem factor a number is not a decision problem.You can make up many decision problems that attempt to capture factoring. Here is one: the language of all quartets $(n,i,j,b)$ such that the $j$th bit of the $i$th prime factor of $n$ is equal to $b$. This language is in NP, since the factorization of $n$ functions as a witness (this uses the fact that primality can be tested in polynomial time; in fact, it is enough to know that primality is in NP, which is an easier fact). It is strongly suspected that this language is not NP-complete.