|
|
|
|
|
by klyrs
681 days ago
|
|
No, IF is unquestionably in NP. The definition of NP is that a purported solution can be checked in polynomial time. That's it. Factorization can be verified by multiplication, in polynomial time, therefore the problem is in NP. Perhaps you're confounding NP with NPC? Recall that P is a subset of NP. Not sure what you mean by "IF's decision problem" though. Primality is in P. |
|
Kinda funny tho we have a categorization system of problems to keep things organized and analogous, but there’s lots of confusion on how it sorts. Haha! :)