3 ms·
You touch on something interesting that I don't see often mentioned with NP-hard problems, and that's the actual inputs for where they're hard. Packing a knaps
by hackcasual 10y ago
You touch on something interesting that I don't see often mentioned with NP-hard problems, and that's the actual inputs for where they're hard.
Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial.
It's often the case that NP real world problems actually have their inputs fall in the easier to solve ranges.
- SilasX 10y ago>Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial. Interestingly, that's the basis of the (now broken) Knapsack cryptosystem -- your private key is an easy knapsack, and you convert it to the public key -- a hard knapsack -- via modular multiplication. You encode your message by your choice of which items from the hard knapsack to add to the sum, which becomes the ciphertext. https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
- hackcasual 10y agoHave you checked out lattice based crypto? It's the spiritual successor to merkel-hellman, based on the hardness of subset sum. I've got a rough presentation from when I talked about it at a reading group: https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-zOLImqzhhX9TX8xrQA71zwNA/edit?usp=sharing https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-z...
- SilasX 10y agoInteresting! I didn't know they were related. Thanks!