Re:A riddle wrapped in a curve
by aparent on Thursday October 22, 2015 @03:45PM
(#10434534)
> 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.
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.