The Hashtable Packing Problem (2020) (opens in new tab)

> But indeed: The abstract Hashtable Packing Problem is strongly NP-complete. We can therefore stop looking for optimal solutions and instead use heuristics (and still sleep well).

It depends on what you mean exactly.

Many instances of NP complete problems are solved optimally all the time, often quite quickly. See eg integer linear programming.

I sit here wondering how Ryan Williams' treatise on Simulating Time in Square-Root Space could be applied to this problem [0]. I guess, to apply it effectively, one would need to express the packing algorithm as a tree-structured computation and implement the Tree Evaluation framework (Cook/Mertz), potentially integrating it with existing heuristic searches ... This would enable space-efficient exploration of hashtable configurations during precomputation, particularly useful for memory-constrained environments.

But its still not clear to me if this would be practically useful enough.

[0] - https://eccc.weizmann.ac.il/report/2025/017/

Just merge all the keys and create a single perfect hash. Packing problem solved. Not NP.