[orlp]

Regarding (b), a non-constructive proof of P=NP does not exist. Because such a proof is immediately constructive.

You can create an enumeration over all Turing machines, and run each of them on the problem, 'diagonally', so we perform one step of computation on machine 1, then 1, 2, 1, 2, 3, 1, 2, 3, 4, etc. This will eventually run each Turing machine for an arbitrary amount of steps. As soon as one of the Turing machines accepts, we also accept.

Suppose the nth Turing machine is our poly time machine we have proven to exist (although we don't know n). It takes n steps of our meta algorithm to run this machine 1 step, then n+1 metasteps for the next step and so forth. In total it takes n + n+1 + ... + n+k = O(k^2 + kn) metasteps to run the nth Turing machine k steps.

But here's the crux... n does not depend on the input size, only on our problem! Thus it is a constant. In other words, this meta algorithm is quadratically worse (due to k^2 steps) than the optimal algorithm, but it is poly time.

Note that the above algorithm doesn't work for co-NP, in which we require that the "no" instances get solved in poly time (in NP we only require the "yes" instances to get solved in poly time).

[dvdkhlng]

In case anyone wonders, I think the same argument is made in a somewhat easier to understand way in one section of the the P vs NP wikipedia page [2].

But I think that would turn (b) into a special case of (a) i.e. a bizarre algorithm that is completely useless. And it would also be an algorithm of mostly unknown complexity (with P=NP, we'd know it to be ∈ P, but we won't necessarily know anything else).

[2] https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

[hnfong]

> You can create an enumeration over all Turing machines

Do you mean "all Turing machines that only accept the 'problem'"?

Because if you literally enumerate over all Turing machines, including trivial ones like those that ignores the input and just acceps/halt no matter what, then it doesn't help you solve the problem at all...

And then the question becomes whether you can enumerate over all Turing machine that accepts only languages of the 'problem'... (or whatever they call it in the standard terminology). I have a feeling this one might not be "computable" regardless of the "input size".

PS: I'm not quite thinking straight now so apologies if I missed something obvious..

[skissane]

> Because if you literally enumerate over all Turing machines, including trivial ones like those that ignores the input and just acceps/halt no matter what, then it doesn't help you solve the problem at all...

I think there is a step which was not explicitly stated in the GP comment. When a given Turing machine accepts, we check whether its output is a valid proof of the answer to our problem. Per definition of NP, we can check that proof in polynomial time. If the check passes, we accept. If the check fails, we ignore that accept and move on.

So we are executing all possible Turing machines in parallel, not just the ones that accept the problem. And when any of them accept, we have to check whether the accept should be ignored or not, because most of the Turing machines are doing something completely unrelated to our problem.

[hnfong]

Yeah after I commented I read the wikipedia link in a sibling comment -- which basically says what you said. Having programs/Turing Machines generate 'proofs' and checking them in P does seems legit.

[vintermann]

> You can create an enumeration over all Turing machines

Wait, can you?

[skissane]

Yes. Every possible Turing machine can be defined using a finite number of symbols drawn from a finite alphabet. Each string in a finite alphabet corresponds to an integer, so for every possible Turing machine there is a corresponding integer. There are many conventions for assigning an integer to each Turing machine, but the choice of convention does not matter (so long as it is computable) - the point is, since we can enumerate the integers, and any computable subset thereof, we can enumerate all Turing machines.

Note this only applies to standard Turing machines (whether single tape or multi-tape, deterministic or non-deterministic). It does not apply to special types of Turing machines such as oracular Turing machines.

[skissane]

This is really a quibble turning on how one defines “constructive”. Let me propose two scenarios, which I will call NC and C. I believe that both scenarios are epistemically possible (given current generally available knowledge), but we do not know if either is logically possible.

In scenario NC, a mathematician devises a highly novel, unexpected and correct proof that P=NP, by finding a way to translate that statement into a statement in some seemingly unrelated area of mathematics, and then using some very deep and profound and innovative techniques to prove that statement in that seemingly unrelated mathematical area. Now, suppose those techniques are fundamentally non-constructive, in that they rely on methods of a kind of which no consistent mathematical constructivist could approve. This kind of proof would not directly turn on finding some novel algorithm for some NP-complete problem and directly proving that the algorithm executes in polynomial time. The only algorithms invoked may be some relatively straightforward algorithms needed to translate P=NP into that very different mathematical area, and then the real genius of the proof may be done in that other area and not explicitly rely on any algorithms at all. This would be a fundamentally non-constructive proof.

By contrast, in scenario C, we have a very different proof that P=NP, which might have as its centrepiece some very novel and obscure and maybe even bizarre algorithm, along with a proof that the algorithm correctly and exactly solves some NP-complete problem, and also a proof that the algorithm executes in polynomial time, and those two proofs may depend on quite subtle details of that specific algorithm. Let us suppose that the profound mathematical genius who devised this algorithm and the associated proofs has great sympathy for mathematical constructivism, and hence does not use in the proof the kinds of techniques of which a mathematical constructivist would disapprove (or, at least, not directly). Maybe even, those proofs are relatively straightforward once you have the algorithm, and coming up with the algorithm was the real genius of the overall proof

Now, you’ve pointed to an example of an already well-known algorithm which solves an NP-complete problem in polynomial time, but only if P=NP. And you are claiming that turns any non-constructive proof into a constructive one. But in scenario NC, our proof was non-constructive in two ways (a) unlike the proof in scenario C, this proof does not have as its centrepiece the construction of a specific example of a novel polynomial time algorithm for solving an NP-complete problem; (b) and unlike the proof in C, it relies on mathematical techniques of which a mathematical constructivist would disapprove. When we combine it with your proposal, it does not alter either of those two ways in which the proof in scenario NC is non-constructive, and so does not actually convert a non-constructive proof into a constructive one as you claim it does.

The term “constructive” has multiple meanings, and even if your argument succeeds in converting a “non-constructive” proof into a “constructive” proof in one sense of “constructive”, it fails to do so in other important senses.