Argument for P=NP

I'm also trying to argue that, if we take non-determinism seriously, in terms of infinite number of deterministic TMs, there is a non-zero probability that we can physically construct such a deterministic TM that will appear experimentally to solve all NP-complete problems in polynomial time.

No, not at all.

Let's take the view of a nondeterministic Turing machine as a Turing machine that can explore unboundedly many branches of computation in parallel: its transition function is actually a multivalued function, so it can transition to more than one state in each step (which can be viewed as making one or more clones of itself that will run in parallel). Each particular one of those parallel branches of computation can be viewed as a deterministic Turing machine that makes "guesses" at various points, and so the nondeterministic Turing machine can be viewed as unboundedly many deterministic Turing machines that make "guesses." This is how you are viewing a nondeterministic Turing machine, is that correct?

By definition, this nondeterministic Turing machine accepts a particular input if any branch of computation accepts that particular input. So, for any particular input, there is some particular "guessing" deterministic Turing machine that will accept that input. But that doesn't mean that the same "guessing" deterministic Turing machine accepts all inputs that are accepted by the nondeterministic Turing machine. Different inputs may be accepted by different branches of computation—different "guessing" deterministic Turing machines. It is entirely possible that none of the branches of computation, no single one of the "guessing" deterministic Turing machines, accepts all inputs that are accepted by the nondeterministic Turing machine. So you cannot say that if the nondeterministic Turing machine solves a decision problem in polynomial time then there must be a particular "guessing" deterministic Turing machine that solves that same decision problem in polynomial time. Even if you have a nondeterministic Turing machine that decides some problem, there is absolutely no guarantee that any particular branch of computation of that machine decides that problem.

Don't confuse a Turing machine that correctly answers "yes" or "no" for some particular instance of a decision problem with a Turing machine that correctly decides the problem itself (i.e., for all instances of the problem). Making a Turing machine that correctly answers "yes" or "no" for some particular instance of a decision problem is easy—just make one Turing machine that always answers "yes," and another that always answers "no," and for any particular instance of a decision problem one of those Turing machines will answer correctly. That is not at all the same as a Turing machine that will answer correctly for all instances of the decision problem.

/r/math Thread