[stephencanon]

> (which is a taller order than just proving P=NP)

A proof that P=NP immediately gives a polynomial-time algorithm for NP complete problems via universal search. It’s so wildly impractical as to probably not change anything, but it _is_ in P.

[Tainnor]

Fair enough, I wasn't aware.

[edanm]

What? That doesn't seem correct to me. (Since I'm not actually that fluent in CS complexity theory, I assume the problem is my understanding.)

Can you explain more about what universal search is, and/or where I can read about how it would solve the problem?

[stephencanon]

The handwavy explanation is you can enumerate a list of all the turing machines. You run the first one for one step, then you run the first two for two steps, then the first three for three steps, etc, until one of them halts. If P=NP, this will happen in polynomial time, which gives you the algorithm you need.

[edanm]

I'm not sure I understand. How would a list of all Turing machines possibly help when trying to solve a specific problem in P time? Are they built in a way that is relevant to the problem you're trying to solve (if so, how?).

[zfnmxt]

Disclaimer: I didn't know about universal search until I read stephencanon's comment. I just thought it was fun to think about and I think the answer is what follows, but it could be wrong!

Imagine your problem is to write Hamlet by Shakespeare. One way to write Hamlet by Shakespeare is to enlist many monkeys who then type at random (but with the property that no two monkeys type the same thing). Each monkey also has a special "done" button that they press when they're done writing. Some monkeys never press it and write forever.

So you instruct each monkey to type one key and then you check each monkey to see if they pressed "done". If they pressed "done", you check if they wrote Hamlet. Otherwise, you continue and have the monkeys each press another key.

Since there are infinitely many different monkeys, so you can't enlist them all at once, because then checking after each key press would take you infinitely long! This is why you play that game with at the first step you enlist one monkey, then two, then three, etc; it ensures at each step there are finitely many monkeys to check.

Of all the possible monkeys, one monkey will write Hamlet exactly and then press "done". This scheme finds that monkey. Similarly, for Turing machines, there will be at least one (technically, infinitely many) that solves your problem. You just have to figure out which one it is by doing the enumeration that stephencanon detailed. 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.

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