10
January 5, 2022
Let’s do something that seems insane at first: let’s try to solve NP-completedecision problems using the “random” outputs of cryptographic hash functions.
It doesn’t matter exactly which hash functions we use. In fact, in thisargument, the hash functions are really a stand-in for any polynomial-timealgorithm, but I want to take advantage of your intuitive sense of whata cryptographic hash function is, so I’m calling them hash functions. Theintuitive properties I want you to have in mind are that they arerandom-behaving and computationally irreducible, i.e. there’s no way to learn orpredict properties of their output without actually computing them.
A bit of notation will help make things clear. Let H1, H2, … be any sequenceof keyed polynomial-time hash functions where Hn takes a key k of size |k|= n as well as an arbitrary-length input x. For every key k, we can define thelanguage HL(k) = { x | H|k|(k, x)’s first bit is 1 }. In other words, for everykey of unbounded size, there’s a language HL(k), and to find out whether astring is in HL(k) you simply hash the string with the key k using the |k|-thalgorithm and check if the first bit of the hash is 1.
Now, here’s the question: If we keep passing bigger and bigger keys to biggerand bigger members of the hash function family, is it possible that we wouldstumble upon some enormous key k such that HL(k) is an NP-complete language? Ifthat happens, then P would equal NP. Although k would be impracticallylarge (probably so large that its length would put even Graham’s number to shame),we could decide an NP-complete language in polynomial time using one call toHn with the hard-coded key. So, could that happen?
There are infinitely many NP-complete languages, so in one sense there areinfinitely many collision targets. Yet, on the other hand, it seems like we needan infinite sequence of ‘accidental’ bit collisions, one for every string, tocollide an entire language.
If the hash functions were truly random, modeled as random oracles, theprobability of a collision would work out to be exactly zero for eachNP-complete language. But that’s a heuristic argument, there’s no realprobabilities involved here! Although we are thinking about the hash functionsas random-behaving, they’re not really random, they’re all deterministiccomputations. A language collision is therefore not ruled out by any statisticalargument.
An information-theoretic argument can’t rule out a language collision either,because NP-complete languages have concise descriptions in the form of theirpolynomial-time solution-checking machine, and k can be arbitrarily large,holding arbitrary amounts of information.
If P is not equal to NP, then for any choice of hash function family,all infinitely-many, arbitrary-length keys k, HL(k) must definitelynever collide with any NP-complete language. If P!=NP weretrue and unprovable, this wouldn’t be so weird, we’d just say that no languagecollision occurs, and that’s just a brute fact about math with no real need fora reason.
However, if P!=NP is true and provable, then this starts to look reallyweird. In this case it looks like whatever logic leads to P!=NP is somehow“forcing” hash functions’ “random” outputs to always miss the NP-completelanguages, or vice-versa "forcing" the NP-complete languages to always miss thehash functions. The logic in the P!=NP proof would need to explain how theseapparently-structureless (and arbitrary-size!) algorithms all have a "global"property of never colliding with an NP-complete language, or explain how theNP-complete languages 'conspire' to disagree with all of the hash functions.
If we had a proof of P!=NP, then we would know for sure that all hashfunctions’ outputs will always miss all of the NP-complete languages,without ever having to evaluate the hash functions! That seemsreally strange, maybe even as strange as a language collision occurring,depending on how much we believe in computational irreducibility.
If P!=NP is provable, then our intuitive notion of cryptographic functionsbehaving randomly, as well as the concept of computational irreducibility,become suspect. If we believe computational irreducibility is real, not justsomething we think is real because we are computationally bounded humans, wemight be tempted to conclude that one of the following conjectures is true:
Conjecture 1: P=NP, but only by accident as described above,for a key so large that we’d never find out. (In this case, P=NP is probablyunprovable, because even if we knew the key and it was small enough to writedown, there's no reason to expect there to be a line of reasoning tying hash function outputsto the NP-complete language. It’s just an accident.)
Conjecture 2: P!=NP, but it’s unprovable, because the existenceof a proof would violate our (admittedly informal) notions of computational irreducibilityand cryptographic security.
But hold on, there are complexity classes known to be larger than P,like EXPTIME and classes containing undecidable languages. Why doesn’t this hashfunction collision trick apply there, too? Why don’t those proofs, the proofthat P!=EXPTIME, and the proof that the halting problem is undecidable, bothalso show that all hash functions have the mysterious language-avoidanceproperty that we’re worried violates computational irreducibility?
The answer can be found in the proofs of those theorems. Both the proof ofP!=EXPTIME through the time hierarchytheorem and the proof that the halting problem is undecidable usediagonalization arguments. They define a language by way of an algorithm whichwould simulate the hash functions (in fact all ‘faster’ algorithms) on someinputs and disagree with them on purpose. Computational irreducibility is notviolated by those results, because the proofs make reference to all ofthe hash functions, reference their evaluations, and then construct analgorithm to disagree with them. In those proofs, it’s not that the hashfunctions’ outputs miss the EXPTIME language or the undecidable language byaccident, it’s exactly the other way around: the EXPTIME language or undecidablelanguage make reference to, and were designed to miss, the hashfunctions.
Because of completeness, i.e. the fact that there are polynomial-time reductionsbetween all NP-complete languages, it's not enough to construct oneNP-complete language that misses the hash functions like in the proofs mentionedabove. In fact, ALL NP-complete languages would have to missALL of the hash functions in order for P to not equal NP. It seems thatit's either some cosmic accident that no collision occurs, or languages like SATand TQBF (in the case of P vs PSPACE) are "secretly" diagonalizing, somehow, todisagree with all possible hash functions.
If this reasoning is correct, then it would explain why we can’t seem to improveour results any better than the time hierarchy theorem allows: irreducibilityensures that diagonalization is the only way to guarantee there isn't a collision.It would also explain why we can’t even rule out linear-time algorithmsfor NP-complete problems like SAT: good symmetric cryptography only needs lineartime, so for all we know the hash function that produces the freak collisionruns in linear time, too. Linear-time (or better) lower bounds for SAT or TQBFwould count as evidence against this idea, since any proof of those resultswould explain to us exactly how at least some of the NP-complete orPSPACE-complete languages are conspiring to miss all of the linear-time hashfunctions, and linear-time hash functions should be just as computationallyirreducible as hash functions with quadratic runtime or greater.
If instead of hash functions, we allowed arbitrary uniformfamilies of polynomial-time functions, then HL(k) equalling an NP-completelanguage for some k would exactly be the definition of P=NP. By restrictingourselves to hash functions, where computational irreducibility makes some kindof intuitive sense, it’s easier to grasp how a proof of P!=NP either needs to dotime-hierarchy-theorem-style diagonalization or exploit a lack of computationalirreducibility present in all hash functions.
Of course this is just an intuitive argument. We haven’t provenanything here. Perhaps it’s possible to formalize some kind of “computationalirreducibility hypothesis” and show that under that assumption, P!=NP isunprovable. That’s left as an exercise to the reader.
Personally, I think P versus NP is the wrong question to care about. If P=NPbecause of an impossible-to-discover collision then who cares? If P!=NP but wecan find machine learning algorithms to solve small cases of "hard" problemsthen who cares? Studying concrete complexity, complexity theory withouthiding constant factors in big-O notation and without hiding exponents in theword “polynomial”, seems like it would be more useful. If we could get good atthat, then we could lower-bound the security of the cryptographic algorithms weactually use, and maybe even lower-bound the size of a freak-collision-producingkey.
Concrete complexity is messy, though, because without big-O notation, themachine model matters, and we pretty much end up with a different “complexitytheory” for every kind of machine. Unfortunately, I think computationalirreducibility will—at least if my intuitive formulation of it is in the ballpark ofwhat's true—prevent us from making much progress there, too.
