5 ms·

Just a thought, just because a general problem is NPHard doesn't mean that we can't find specific solutions quickly or that a given input is hard to search for.

Just a thought, just because a general problem is NPHard doesn't mean that we can't find specific solutions quickly or that a given input is hard to search for. If the downstream effect results in an order of magnitude less work, it makes sense, it's just a tradeoff.

bawolff 2y ago
Well yes, heurstics for query planning is a very well researched field
- 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 ago
    Most 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 ago
      What complexity class will be the problem of construct only hards to solve knapsack (or others) problems?
      - eru 2y ago
        For 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.
somat 2y ago
The one I liked was the postgres genetic optimizer. https://www.postgresql.org/docs/17/geqo-pg-intro.html https://www.postgresql.org/docs/17/geqo-pg-intro.html The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search. My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed at some point, but I see it mentioned in current docs, so I am probably wrong about that. Anyway I wonder if, with some of the new advances in machine learning, it would be worth revisiting this approach to optimization.
- thesz 2y ago
  As you mentioned machine learning, a useful way to implement inference in language models is to use a beam search: https://en.wikipedia.org/wiki/Beam_search https://en.wikipedia.org/wiki/Beam_search Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html

bawolff 2y ago

Well yes, heurstics for query planning is a very well researched field

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 ago
  Most 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 ago
    What complexity class will be the problem of construct only hards to solve knapsack (or others) problems?
    - eru 2y ago
      For 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.

somat 2y ago

The one I liked was the postgres genetic optimizer. https://www.postgresql.org/docs/17/geqo-pg-intro.html https://www.postgresql.org/docs/17/geqo-pg-intro.html The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search. My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed at some point, but I see it mentioned in current docs, so I am probably wrong about that. Anyway I wonder if, with some of the new advances in machine learning, it would be worth revisiting this approach to optimization.

thesz 2y ago
As you mentioned machine learning, a useful way to implement inference in language models is to use a beam search: https://en.wikipedia.org/wiki/Beam_search https://en.wikipedia.org/wiki/Beam_search Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html