Re:Quantum Advantage for NP Approximation
by Xcelerate on Thursday October 10, 2024 @09:34AM
(#41798646)
> 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.
Re:Quantum Advantage for NP Approximation
by zero_k on Thursday October 10, 2024 @10:58AM
(#41799531)
Other 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.
Re:Quantum Advantage for NP Approximation
by Xcelerate on Thursday October 10, 2024 @01:01PM
(#41800867)
Haha, 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.
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.