[mathgradthrow]

We already have such a machine. If P=NP then there is some Turing machine that produces, for instance, a 3-SAT certificate in polynomial time.

We may enumerate the turing machines and call ours the M-th one. Given a boolean expression P, increment a counter N and run the first N turing machines on P for N steps, check each of the outputs of these against the certificate checker.

If M runs in time O(|P|^n) and the certificate checker is O(|C|^m) and then our hybrid machine runs in something like O((M+|P|^n)^2m).

All we're missing is a proof.

[gowld]

My point is that N is most probably bigger than the entire Universe, if it turns out to be finite.