My survey article on P vs. NP (2017)

Re:My survey article on P vs. NP (2017) by tgflynn on Tuesday March 23, 2021 @12:12PM (#26556711)

If there's an efficient algorithm for solving NP-complete problems then 99% of current cryptography would be broken. Only one-time-pads would still be secure.

But don't worry, if that happens the world would be so different there might no longer be a need for cryptography.

[ Parent | on HN ]

Re:My survey article on P vs. NP (2017) by rrobukef on Tuesday March 23, 2021 @12:18PM (#26556780)

There exist crypto systems independent on P vs NP, both symmetric and asymnetric. The general approach exploits polynomial time complexity differences. However key-sizes increase accordingly: last I saw a key-pair was a few 100's of megabytes. (an enourmous reduction from originally GB's)

[ Parent | on HN ]

Re:My survey article on P vs. NP (2017) by tgflynn on Tuesday March 23, 2021 @12:22PM (#26556821)

But there aren't a lot of proven bounds on polynomial time complexity either. For all we know it may be possible to solve 3-SAT in linear time.

[ Parent | on HN ]