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.
Hashtable packing can be solved in O(n) space: just try out all possible combinations of offsets. To improve on this with square-root-of-time space, you would need an algorithm that takes o(n²) time, but since hashtable packing is NP-complete, the existence of such an algorithm would imply P = NP.
Comments
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/
Hashtable packing can be solved in O(n) space: just try out all possible combinations of offsets. To improve on this with square-root-of-time space, you would need an algorithm that takes o(n²) time, but since hashtable packing is NP-complete, the existence of such an algorithm would imply P = NP.