3 ms·
Take your favorite hash function, and view it as inducing a directed graph on the set of its possible outputs. Finding a cycle is hard! (except, most hash fun
by klyrs 2y ago
Take your favorite hash function, and view it as inducing a directed graph on the set of its possible outputs. Finding a cycle is hard! (except, most hash functions map 0->0 for "nothing up my sleeves" appeal)
But also, it's ridiculously hard to answer simple questions about such graphs, such as listing its nodes.
- adzm 2y agoI can't even think of a hash function that maps 0 to 0
- adrianN 2y agoSince there are uncountably many functions, the functions we can think of have measure zero in the set of all functions.
- deleted 2y ago[deleted]
- foota 2y agoInterestingly, CRC32C is a bijective function over 4 byte integers. More generally, any perfect minimal hashing function could be used to map a set of N integers to the numbers 1 through N.
- ithinkso 2y ago> Finding a cycle is hard! I mean, it is easy in the size of the graph, you constructed implicitly an exponentially large graph, I don't think it's in the spirit of GP point where the hamiltonian cycle is exponentially (in the size of the graph) hard to find