3 ms·
> Random k-SAT is useless Other than cryptography, is there any real-world value in solving random problem instances of NP-complete problems (at least when ave
by Xcelerate 2y ago
> Random k-SAT is useless
Other than cryptography, is there any real-world value in solving random problem instances of NP-complete problems (at least when average case approaches worst case, based on the parameterization of the problem)? Presumably these are instances that do not have any underlying mathematical structure as a truly random problem instance is Kolmogorov-maximal, and thus even if you solve the problem via brute-force, the result still isn't useful for any predictive purpose.
- zero_k 2y agoOther than cryptography? Like, you see a use-case for it there? Please do educate me! IMO there's nothing there. It's a barren landscape. The desert is more alive.
- Xcelerate 2y agoHaha, I was more so meaning that cryptography depends on the actual existence of hard problem instances, which appears to be the case but hasn’t been conclusively proved.