[edanm]

> If P = NP, that enumeration process can happen in P time. Keep in mind that all problems in NP have polynomial time verifiers. So you can always check a solution (i.e., checking if the monkey actually wrote Hamlet) in polynomial time.

I understand why verifying can happen in time P for each machine, but I'm still confused on how you're sure that you hit on the right machine in P time.

For writing Hamlet, you have way more than "P" options for machines, if you're typing at random (I'm not sure how you'd define the input in this case, maybe the length of the work you want them to write?). So even if you can verify in time P, you'll still need to go through way-more-than-P machines before one solves your problem.

Maybe there is a way to use universal search or something to make this happen faster, but I'm not sure how a non-constructive P=NP proof actually gives you the algorithm.

(I tried looking a bit into this and I didn't yet find something that shows otherwise, but I didn't have time to look much.)

[zfnmxt]

> I understand why verifying can happen in time P for each machine, but I'm still confused on how you're sure that you hit on the right machine in P time.

My monkey stuff was a bit wrong; the enumeration stuff actually goes like this: let every binary string be a Turing machine. So TM 0 is the string 0, TM 1 is the string 1, TM 2 is 10, and so on. Every possible TM machine can be encoded in this way.

For half your time steps, run TM 0. For half of the remaining time steps, run TM 1. For half of those, run TM 2. So the sequence of execution actually looks like this:

0, 1, 0, 2, 0, 1, 0, 3, ...

This means that every 2^(n+1) steps, the nth TM does 1 step of computation. Say that the kth TM is the smallest TM that solves your problem. Then it takes 2^(k+1) * O(m^c) steps to solve your problem, where O(m^c) is a polynomial bound. (I've ignored accounting for the time for verification, but that's polynomial too, so it doesn't matter.) That O(m^c) comes from the fact that we know that a polynomial time algorithm exists for our problem (but we don't know what it is), since P = NP.

But 2^(k+1) is a constant; it doesn't depend on the input size. The smallest program that solves our problem (in general) will always be the kth program. (Technically on some inputs there will be smaller programs that solve the input just by getting lucky, but TM k is the smallest program that solves our problem for all inputs.) So 2^(k+1) * O(m^c) is a polynomial number of steps, just with an absurdly huge constant of 2^(k+1).

I found [1] to be helpful and it probably explains it better than I just did.

[1] https://steemit.com/steemstem/@markgritter/leonid-levin-s-un...

[edanm]

I still don't see how you can be confident that the Turing Machine that solves your problem isn't an exponential amount "down" in the list of Turing machines. What if its size is 2^n for problem size n?

Also, more importantly, I still don't see how Universal Search solves what parent actually said, which is that even without knowing the algorithm this will work. The link you added seems to suggest you need to know the actual P algorithm for this to work.

[stephencanon]

It doesn't matter how far down it is. It has some constant index independent of the problem size, so for "large enough" problems, it's just a constant factor on the time required.