*(Updated in light of the revised question)*

If such a map exists (and the input machine comes with an integer $k$ certifying that $n^k+k$ is an upper bound on the machine's running time), then the map is computable, as follows.

If the map exists then $P=NP$, so there is a polynomial time reduction $R$ from the Bounded Halting Problem (given an nondeterministic machine $N$, string $x$, and integer $k$ written in unary, does $N(x)$ accept within at most $k$ steps?) to a specific $P$-complete language, e.g. Circuit Evaluation. So given a nondeterministic machine $N$ that's supposed to run in say $n^c+c$ time, here is the pseudocode you output for your polytime algorithm:

"Given $x$, form the Bounded Halting instance $\langle N,x,1^{|x|^c+c}\rangle$, apply the reduction $R$ from Bounded Halting to Circuit Evaluation to this instance, get a circuit $C$ with input $v$, then evaluate $C$ on $v$ in polynomial time, accept iff $C(v)=1$."

**For your more general question.** Suppose we only assume $P=NP$, and now we are just given arbitrary nondeterministic machines and want to output an equivalent deterministic machine which runs in polytime when the input machine is a nondeterministic polytime machine. Observe there are generally two possible ways to define "nondeterministic polytime machine" when you do not enforce a polytime counter on the machine:

*Def. 1.* There is a $c$ such that, on all inputs $x$, every possible computation path takes at most $|x|^c+c$ steps. (This is the usual definition.)

*Def. 2.* There is a $c$ such that, on all inputs $x \in L$, there is an accepting computation path that takes at most $|x|^c+c$ steps.

I'm not sure which definition you intended.

Let's first treat definition 1. Let the "Bounded Path Problem" be: given an nondeterministic machine $N$, string $x$, and integer $k$ written in unary, do all computation paths on $N(x)$ stop (accept or reject) within at most $k$ steps? This is $coNP$-complete and thus has a reduction $R'$ to Circuit Evaluation. Given a nondeterministic machine $N$ here is pseudocode to output for your polytime algorithm:

"Given $x$, for all $k=1,2,\ldots$: form the Bounded Path instance $\langle N,x,1^{k}\rangle$, apply reduction $R'$ from Bounded Path to Circuit Eval, evaluate the resulting circuit. If the circuit evaluates to $1$, then break out of the for loop on $k$, apply the reduction $R$ from Bounded Halting to Circuit Evaluation to $\langle N,x,1^{k}\rangle$ to determine if $N(x)$ accepts."

The for-loop just sets $k$ to be the maximum length of a computation path of $N(x)$. For those nondeterministic machines which fit definition 1, the resulting algorithm runs in polynomial time. In fact there's a fixed constant $c$ such that for every nondeterministic machine with all paths of length at most $t(n)$, the above pseudocode for a deterministic machine runs in $O(t(n)^c)$ time.

What about definition 2? Not sure at the moment. Probably there is a simple solution for it too (regardless of what the answer is). Maybe I should first confirm that you care about definition 2.

somelanguage produce a deterministic machine that accepts the same language. $\endgroup$ – Tom Ellis Jun 11 '10 at 20:46