Non-existence of algorithm converting NP algorithm to P algorithm? - MathOverflow

Non-existence of algorithm converting NP algorithm to P algorithm?

2010-06-11T20:34:41Z

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is equivalent to the existence of a map of the following form:

Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L) [Edit: we are not to assume these NDTMs come with any certificate proving they run in polynomial time -- Ryan requested this clarification, below]
Output: a polynomial-time deterministic Turing machine which accepts the language L

Is it known that if such a map exists then it cannot be computable?

Answer by Nate Eldredge for Non-existence of algorithm converting NP algorithm to P algorithm?

2010-06-11T20:59:32Z

Unless I misunderstand, existence of such an algorithm would be equivalent to P=NP. Obviously if it exists then P=NP. Conversely, if P=NP then there is a polynomial time algorithm for (say) 3SAT. So given a nondeterministic Turing machine M, produce a deterministic machine that converts M into an instance of 3SAT (in polynomial time), and then executes the aforementioned algorithm on it.

Answer by Ryan Williams for Non-existence of algorithm converting NP algorithm to P algorithm?

2010-06-12T06:56:45Z

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

Answer by Timothy Chow for Non-existence of algorithm converting NP algorithm to P algorithm?

2010-06-16T17:40:23Z

The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be unclocked NP machines then nothing useful can possibly be computed from the input, as explained in the answer to this related MO question by Joel David Hamkins. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has absolutely nothing at all to do with P or NP. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a clocked NP machine, then Cook's reduction shows how to construct a P machine that solves your problem (assuming P = NP). This is really what we care about in practice. If I have a problem that I know is in NP, then I want a mechanical way of producing a polytime algorithm for it (assuming P = NP). It's really irrelevant that there are all kinds of other, bizarre NP machines that accept the same language, and that it's an uncomputable task to sift through them.