Say I have a number 45
What are the factors of 45?
1, 3, 5, 9, 15, 45
Is 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 says
Okay, 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 NP
Say n is a number
Say S is a set of numbers between 1 and n
Is S the set of ALL factors of n or not.
A program should say it's false when
- One 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?