"One thing about a positive P=NP proof is that it would necessarily be constructive"
I don't see why that would necessarily be true. For example, let's say that I show that, if P != NP, the set of all NP-complete problems can be split into N equivalence classes and then produce N+1 NP-complete problems that are pairwise in different equivalence classes.
Alternatively (and, I'm guessing, slightly more realistic), one might define a Turing-equivalent machine and show that, if there is any room between P and NP, for that machine, any program that solves a NP-complete problem can be reduced to run for one less time step.
Comments
"One thing about a positive P=NP proof is that it would necessarily be constructive"
I don't see why that would necessarily be true. For example, let's say that I show that, if P != NP, the set of all NP-complete problems can be split into N equivalence classes and then produce N+1 NP-complete problems that are pairwise in different equivalence classes.
Alternatively (and, I'm guessing, slightly more realistic), one might define a Turing-equivalent machine and show that, if there is any room between P and NP, for that machine, any program that solves a NP-complete problem can be reduced to run for one less time step.
Can you explain?