3 ms·
This.
by charrisku 11y ago
This.
- wolfgke 11y agoAsymmetric crypto clearly is in NPcomplete. What one can not prove yet is that some crypto system is in NPcomplete \ P (since this would imply P != NP).
- aparent 11y ago> 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.
- wolfgke 11y agoSorry, I was typing NPcomplete and meant NP. :-(