3 ms·
I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.
by alexey-salmin 2y ago
I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.
- Vervious 2y agoThat's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.