4 ms·
Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one
by foota 2y ago
Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one with no overlapping vertices visited twice).
I don't know how hard it is to generate graphs that are hard to find simple cycles in though. For example, previous work showed that random graphs are likely to contain hamiltonian cycles (and with this algorithm they can now be found).
- klyrs 2y agoTake 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