6 deleted 32 characters in body

(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:

Consider the following code:

"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.

5 added 1583 characters in body; added 1 characters in body

(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 it 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(we typically assume that the machine's running time is easily inferred from the code of the machine, see the comments below for an explanation of how to enforce this condition), here is the pseudocode you output for your polytime algorithm:

Why do

For your more general question. Suppose we only assume that (an upper bound on) the machine's running time can be inferred from the code of the machine? If we did not have this condition then $P=NP$, and now we could not effectively certify if a are just given arbitrary nondeterministic machines and want to output an equivalent deterministic machine really which runs in polynomial time or 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. (indeed, as noted belowThis is the usual definition.)

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

I'm not certify if a sure which definition you intended.

Let's first treat definition 1. Let the "Bounded Path Problem" be: given an nondeterministic machine runs $N$, string $x$, and integer $k$ written in finite time unary, do all computation paths on $N(x)$ stop (accept or not). reject) within at most $k$ steps? This is related $coNP$-complete and thus has a reduction $R'$ to why certain randomized classes like Circuit Evaluation. Given a nondeterministic machine $BPP$ are not known N$here is pseudocode to have complete languagesoutput for your polytime algorithm:we do not know a recursive enumeration Consider the following code: "Given$x$, for all$k=1,2,\ldots$: form the two-sided error randomized polytime machinesBounded Path instance$\langle N,x,1^{k}\rangle$, but we have one 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 timemachines. 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. 4 added 76 characters in body; added 113 characters in body If such a map exists then it 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 (we typically assume that the machine's running time is easily inferred from the code of the machine)machine, see the comments below for an explanation of how to enforce this condition), 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$." Why do we assume that (an upper bound on) the machine's running time can be inferred from the code of the machine? If we did not have this condition then we could not effectively certify if a given machine really runs in polynomial time or not (indeed, as noted below, which is necessary we could not certify if a given machine runs in order to have complete languagesfinite time or not). (This is related to why certain randomized classes like$BPP\$ are not known to have complete languages: we do not know a recursive enumeration for the two-sided error randomized polytime machines.)machines, but we have one for the nondeterministic polynomial time machines.

3 added 243 characters in body
2 added 1 characters in body
1