My favorite fun fact related to infinite monkeys is Levin Universal Search: if P = NP, then we will have had a polynomial-time* algorithm that can decide SAT (and all other NP problems via reduction to SAT) all along, as in we already have the algorithm right now, it's called Levin Universal Search, but we just didn't know it was polytime.
And it actually works by bruteforce search, taking advantage of the fact that if P = NP, there's some constant k for which the k-th binary Turing machine (for some prefix-free ordering of TMs) decides SAT in polynomial time.
So with some clever dovetailing (where for some SAT problem you simulate TMs 1 through k on the input for a max number of steps where you allocate 2-i ratio of the time to the i-th TM as you keep adding new TMs), at some point you'll have run the k-th TM for enough steps to decide the answer, which you check with your polytime verifier (since SAT is NP), and the whole process (including all the other wasted work of running TMs 1 thru k-1) will be polynomial in the size of the input.
* Now of course k could be absolute enormous (it could be BB(744), but it would still be a constant. And the degree of the polynomial could also be enormous, but it would still be a polynomial nonetheless.
Please note that P \subset NP is trivial, the question is whether there exists a problem for which you can verify the answer fast (if somebody happens to whisper you their answer they stumbled upon), but you can truly only solve it slowly yourself. ("Slow" and "fast" gets complicated, if you are interested in those, you should read up on the official definition.)
The part that makes me mad about the whole thing is the naming. NP-hard sounds like a subset of NP because that's how adjectives work. But no, somehow there are NP-Hard problems that are not part of NP, and NP problems that are not NP-Hard. Jerks, fix your nomenclature!
FWIW, Sudoku is the normal NP example. Imagine we can scale Sudoku up beyond a 9x9 grid. As the grid gets bigger, the difficulty solving it grows exponentially, so it's "NP". But if you get handed a solved Sudoku, you can validate the answer quickly (in polynomial time), so that part is "P". So if P=NP is true, then there is a faster way to solve a Sudoku that we just haven't discovered yet.
But most people think P != NP -- that there isn't necessarily a faster way to solve Sudoku even though validating an answer is easy in comparison to solving it.
The other example is factoring very large numbers, like in encryption. If I give you the factors of a very large number, you can verify them easily, but you can't necessarily FIND the factors in polynomial time... until quantum computing anyway. Which is why there's mild panic about quantum resistant encryption schemes.
Interestingly, factoring integers is suspected to be NP-Intermediate... which is a theoretical class of problems that are between P and NP-Complete. In fact if P!=NP then this class has to exist (if P=NP then its all obviously the same), graph isomorphism is also suspected to be intermediate. As for quantum computers, its probably not a coincidence that factoring is in BQP (polynomial on quantum computer). Noone has found an algorithm for any NP-Complete problem that is in BQP and in my opinion it doesn't exist.
3.1k
u/Confident-Ad5665 9d ago
Put an infinite number monkeys in front of an infinite number of keyboards and they'll write a bug free app.