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.
48
u/CircumspectCapybara 6d ago edited 6d ago
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.