9
$\begingroup$

[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?

$\endgroup$
15
  • 1
    $\begingroup$ There is no algorithm even for checking whether the non-deterministic Turing machine decides a language L (by the unsolvability of the halting problem). $\endgroup$ Jun 11, 2010 at 20:37
  • $\begingroup$ I'm not asking to check whether the input determines L, but whether, given that the input does accept some language produce a deterministic machine that accepts the same language. $\endgroup$
    – Tom Ellis
    Jun 11, 2010 at 20:46
  • $\begingroup$ I removed my (wrong) previous comment. This question appears to be much more interesting than it seemed at first glance. $\endgroup$ Jun 12, 2010 at 1:21
  • 2
    $\begingroup$ Tom, Adam's point is that we cannot computably recognize such programs---it is a nondecidable set of programs. Nevertheless, there is an easily recognized subclass of these problems which cover all the P sets, namely, those that we can easily observe have a polynomial counter built in that makes them halt in polynomial time, but the question is asked for a transformation of all polytime programs, not just those of a special form. This is the uniformity issue that arose in the comments to Nate's answer below. $\endgroup$ Jun 12, 2010 at 11:41
  • 1
    $\begingroup$ @Tom: You should rewrite your question if you do not assume your input is "verifiably NP". If you open up any text in complexity and see "...given a nondeterministic polytime machine...", that is referring to an object from the set of all nondeterministic machines augmented with a polynomial time counter. $\endgroup$ Jun 12, 2010 at 12:55

3 Answers 3

10
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ "We typically assume that the machine's running time is easily inferred from the code of the machine" -- that seems like a rather strong assumption. How might you go about computing whether the running time is finite or infinite? (obviously an easier problem that computing its precise running time!) $\endgroup$
    – Adam
    Jun 12, 2010 at 8:03
  • 1
    $\begingroup$ Ryan, I’m sceptical too; deciding whether a TM runs in polytime is undecidable (is invoking Rice’s theorem enough to prove it?). I can’t immediately dismiss that knowing that the running time is polynomial might help finding the actual polynomial, but it doesn’t seem very convincing to me either. On the other hand, trying to use some form of the bounded halting problem might be a good idea. $\endgroup$ Jun 12, 2010 at 9:31
  • $\begingroup$ The alternative problem, of "given a nondeterministic machine which just so happens to run in polynomial time but has no built-in guarantee of the actual polynomial, output an equivalent deterministic machine which runs in polytime" is too strong, considering that no complexity theorist ever deals with the input objects. $\endgroup$ Jun 12, 2010 at 12:31
  • $\begingroup$ The NP machines are typically constructed by taking an enumeration of nondeterministic Turing machines {N_i} and augmenting that with an enumeration (over all k) of "polynomial alarm clocks", so that the pair <N_i,k> denotes a machine that runs in at most n^k+k time on all inputs of length n, and after which it just rejects. That is, the set of NP machines is denoted by the set of all pairs {<N_i, k>}. This is quite standard and goes back to Hartmanis and Stearns' original paper on computational complexity. $\endgroup$ Jun 12, 2010 at 12:44
  • 1
    $\begingroup$ Ryan, could you please explain why "no complexity theorist ever deals with the input objects"? After all, those input objects are exactly those which accept an NP language (as opposed to a language which can be proved to be NP). $\endgroup$
    – Tom Ellis
    Jun 12, 2010 at 18:01
4
$\begingroup$

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.

$\endgroup$
7
  • 5
    $\begingroup$ Moreover, there is a cute fact of Theoretical CS: There is a specific explicit algorithm $A$ such that, if there is any polynomial time solution to $SAT$, then $A$ is a polynomial time solution to $SAT$. See Theorem 2 of scottaaronson.com/blog/?p=392 . So, even if someone were to give a non-constructive proof that $P=NP$, you would still have a completely explicit algorithm to run on the 3SAT problem that Nate constructs. $\endgroup$ Jun 11, 2010 at 21:05
  • $\begingroup$ I guess what I need to know is: is the map taking each Turing machine M to (M's reduction to 3SAT) itself a computable map? $\endgroup$
    – Tom Ellis
    Jun 11, 2010 at 21:06
  • 2
    $\begingroup$ @Nate Eldredge: I think there’s a missing step (but maybe it was just implied). The full story should be: given a NDTM N, construct a DTM M which, on input x, builds a Boolean formula φ(N,x), whose meaning is “there is an accepting computation of N on x”, then checks whether it can be satisfied by using the polytime DTM for SAT. The machine M, in turn, runs in polytime. $\endgroup$ Jun 11, 2010 at 23:39
  • 5
    $\begingroup$ Nate, is your argument correct? There is a hidden uniformity assumption. Given the original nondeterministic algorithm p, we know it reduces to 3-Sat, but how to we know which reduction function does the job? Antonio's suggestion is helpful, but I don't see how it solves the issue, since we do not seem to know how big the coefficients or degree of the reduction polynomial will be, and so we cannot seem to uniformly bound the required size of $\varphi(N,x)$. Thus, I don't see why the map $N\to M$ will be polytime. $\endgroup$ Jun 12, 2010 at 0:44
  • 2
    $\begingroup$ Joel, you’re right. Cook’s reduction of an arbitrary problem in NP to SAT depends not only the NDTM to “simulate”, but also on the polynomial that bounds its running time, which we are not given as input (and we cannot compute from N). Now, not only I don’t see that the map N ↦ M should be polytime, but it’s not clear to me that it can be computable at all. $\endgroup$ Jun 12, 2010 at 1:04
3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Ryan's answer above states that there is a computable mapping from unclocked NP machines to P machines. I haven't understood his answer yet, but that's unmistakably what he's claiming. $\endgroup$
    – Tom Ellis
    Jun 16, 2010 at 18:06
  • $\begingroup$ The difference here seems to be the distinction between "definition 1" and "definition 2". In the other question, we were looking at Turing machines that we know accept in polynomial time; this is more similar to definition 2 than to definition 1. Except we were looking at total polynomial-time functions, while definition 2 is about NP-semi-decidable sets. $\endgroup$ Jun 16, 2010 at 18:39
  • $\begingroup$ @Tim: In fact, it's only uncomputable if you insist on a non-standard definition of nondeterministic time. @Tom: I would be happy to answer your questions about my answer... $\endgroup$ Jun 16, 2010 at 20:07
  • $\begingroup$ I somehow missed the fact that Ryan updated his answer. I see that he exploits the fact that in your statement of the problem, you don't require your output to be clocked either. I guess if you consider that to be "useful output" then what I said isn't quite right. If that is really what you are looking for then perhaps I should delete my answer as not addressing your question. $\endgroup$ Jun 16, 2010 at 20:25
  • $\begingroup$ I'm really not sure what I'm looking for as I have no experience of complexity theory, and this question just came into my head one day. It's served a good purpose, which is to give me plenty to think about in this field. Thanks for all your help everyone and when I slowly work through your writings I'll let you know if I have further questions! $\endgroup$
    – Tom Ellis
    Jun 16, 2010 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.