Non-existence of algorithm converting NP algorithm to P algorithm? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:55:44Z http://mathoverflow.net/feeds/question/27867 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27867/non-existence-of-algorithm-converting-np-algorithm-to-p-algorithm Non-existence of algorithm converting NP algorithm to P algorithm? Tom Ellis 2010-06-11T20:34:41Z 2010-06-16T17:40:23Z <p>[Edit: in the light of Nate Eldredge's answer below I rephrase the question]</p> <p>P=NP is equivalent to the existence of a map of the following form:</p> <ul> <li><p>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]</p></li> <li><p>Output: a polynomial-time deterministic Turing machine which accepts the language L</p></li> </ul> <p>Is it known that if such a map exists then it cannot be computable?</p> http://mathoverflow.net/questions/27867/non-existence-of-algorithm-converting-np-algorithm-to-p-algorithm/27870#27870 Answer by Nate Eldredge for Non-existence of algorithm converting NP algorithm to P algorithm? Nate Eldredge 2010-06-11T20:59:32Z 2010-06-11T20:59:32Z <p>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.</p> http://mathoverflow.net/questions/27867/non-existence-of-algorithm-converting-np-algorithm-to-p-algorithm/27910#27910 Answer by Ryan Williams for Non-existence of algorithm converting NP algorithm to P algorithm? Ryan Williams 2010-06-12T06:56:45Z 2010-06-13T05:50:32Z <p><em>(Updated in light of the revised question)</em></p> <p>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. </p> <p>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:</p> <blockquote> <p>"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$."</p> </blockquote> <p><strong>For your more general question.</strong> 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:</p> <p><em>Def. 1.</em> 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.)</p> <p><em>Def. 2.</em> 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.</p> <p>I'm not sure which definition you intended.</p> <p>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:</p> <blockquote> <p>"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."</p> </blockquote> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/27867/non-existence-of-algorithm-converting-np-algorithm-to-p-algorithm/28417#28417 Answer by Timothy Chow for Non-existence of algorithm converting NP algorithm to P algorithm? Timothy Chow 2010-06-16T17:40:23Z 2010-06-16T17:40:23Z <p>The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be <i>unclocked</i> NP machines then nothing useful can possibly be computed from the input, as explained in the answer to <a href="http://mathoverflow.net/questions/28056/given-a-polynomial-time-algorithm-can-we-compute-an-explicit-polynomial-time-bou/28060#28060" rel="nofollow">this related MO question by Joel David Hamkins</a>. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has <i>absolutely nothing at all to do with P or NP</i>. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a <i>clocked</i> 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.</p>