3 ms·
I was more thinking about solving NP hard problems. Modern CPUs are fast, if the benefit is worth it against the downstream task, just do it.
by PartiallyTyped 2y ago
I was more thinking about solving NP hard problems. Modern CPUs are fast, if the benefit is worth it against the downstream task, just do it.
- eru 2y agoMost instances of most NP hard problems are fast and easy to solve in practice. Eg you have to go to quite a bit of effort to construct a knapsack problem that's hard to solve.
- DHRicoF 2y agoWhat complexity class will be the problem of construct only hards to solve knapsack (or others) problems?
- eru 2y agoFor knapsack, you can do that easily in polynomial time. Well, given a few minimal assumptions, like P!=NP; because otherwise there are no hard instances. First, you start with an NP problem where virtually all instances are expected to be hard, like finding the pre-image to a given sha256 hash digest. Second, you sample a random instance in O(n). Third and last, you reduce this problem from the original sha256 inversion to knapsack. You can do this in polynomial time, because knapsack is NP complete. Note for the pedantic: inverting sha256 is certainly in NP, but it's not expected to be NP complete. Second note for the pedantic: because sha256's digest has a specific fixed size, you can technically solve any problems around it in constant time with a big lookup table. So you should replace sha256 in my example with any other problem that's expected to be hard on average.