Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

You are conflating.

Integer factorization is unsolved and it’s decision problem is in NP.

IF’s decision problem’s complexity “may be in NP” because the question of whether P equalling NP is unknown.

Meaning IF is NP, but may well be P if P=NP. If P!=NP then IF is NP.



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.


This! People get a bit confused by the classes: i have been. But they’re pretty simple, especially when explained like that.

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! :)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: