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

> Asymmetric crypto clearly is in NPcomplete

To be in NP-complete a problem must both be in NP and every problem in NP must have a polynomial time reduction to it. This means that NP-complete is fully contained in NP and in fact smaller if P!=NP.

For example P is contained in NP and if P!=NP then no problems in P are in NP-complete.



Sorry, I was typing NPcomplete and meant NP. :-(




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: