|
> 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... |
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.