Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items.

I know that there are algorithms that can help you achieve this by finding salt values to use with a given hash function that will cause this to happen (like this one http://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/).

However, all of the algorithms I've seen are randomized/probabilistic: e.g., there is a probability $p$ for any particular salt value to yield a perfect hash, so keep trying until you find one.

Is there any deterministic algorithm for constructing a perfect hash?

Second, is there a deterministic algorithm to construct a perfect hash that is minimal in size (the smallest program that is a valid perfect hash on these $M$ items)?

Security isn't a concern, and while efficiency of the algorithm to find the mapping is nice, it isn't a requirement. Evaluating whatever mapping program was found should be as efficient as possible though.

• The probabilistic approaches do work well, for sure. Just curious if there are known non probabilistic techniques, or promising avenues which may get even part of the way there. Dec 16 '15 at 18:07
• I've edited the question to try to make it tighter. However, I still find the requirements unclear. If all you want to know is: does a deterministic algorithm exist? the answer is yes, but it might be very slow. Are you looking for an efficient deterministic algorithm? If so, you should edit the question to clarify how efficient you want it to be. I also recommend you edit the question to clarify what assumptions we're allowed to make. For instance, assuming that AES is secure or factoring is hard, it's not hard to find constructions.
– D.W.
Dec 16 '15 at 18:11
• Thanks for the edits, they are good improvements. I'll update per your instructions, but I'm wondering, does your example of assumptions actually pertain to the problem, or is it just a general example? I'll add it to the question, but security isn't a concern, and while efficiency of the algorithm to find the mapping is nice, it isn't a requirement. Evaluating whatever mapping program was found should be efficient though. Dec 16 '15 at 18:33
• Those are examples of assumptions that suffice, for derandomizing randomized algorithms (what does security have to do with it? a cryptographically-secure pseudorandom number generator can be used in place of a true-random number generator, because cryptographic-security means that no polynomial-time algorithm can tell that it is received pseudorandomness rather than real randomness). It's an open question whether P = BPP, but under certain plausible assumptions (e.g., that factoring is hard), we can convert randomized algorithms into deterministic algorithms.
– D.W.
Dec 16 '15 at 20:32

There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency. For instance, you can enumerate all programs (in order of increasing size) and test each one to see which is the first that produces a valid perfect hash. This is a valid deterministic algorithm that is guaranteed to always find a valid perfect hash (and even to find the minimal such program). However, this will be extremely slow for all but the smallest values of $M$, so it's not likely to be useful in practice.
I expect that finding the smallest such program will be NP-hard, and probably $\Pi_2$-hard (loosely, "even harder than NP-hard"). I don't have a proof of this -- just a suspicion. For example, the problem of circuit minimization is known to be $\Pi_2$-hard. In other words, given a circuit $C$, it's $\Pi_2$-hard to find the smallest circuit $C'$ that computes the same function as $C$. Your probably isn't quite the same, but it has a "similar feel", so I would expect your problem (finding the smallest deterministic program that yields a valid hash for the $M$ items) will also be hard.