Polytime algorithm for SUBSET-SUM assuming P=NP
I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to verify the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone actually constructs an algorithm to any NP-complete problem, such as SAT. 

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.