3
$\begingroup$

This is a more precise version of that question.

Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$.

Update Let us assume, as Joel suggested below that $M$ terminates on every input. The simplest thing to assume is that if $u\in L$, the TM eventually gives "yes" and if $u\not\in L$, it gives "no".

The smallest time (number of steps) of such a computation is denoted by $T_M(u)$. For every $n\ge 1$ we define $T_M(n)$ the maximum of all $T_M(u)$ for all accepted $u$ of length $\le n$. Then $T_M(n)\colon \mathbb{N}\to \mathbb{N}$ is the time function of $M$. If $M$ is a deterministic Turing machine, then its time function $T(n)$ is constructible that is there is a deterministic Turing machine which computes values $T(n)$ in time $\sim T(n)$.

Question Let $T(n)$ be the time function of a non-deterministic TM. Is it constructible? Is it {\it polynomally time constructible} that is there is a deterministic TM computing $T(n)$ in time $\sim T(n)^d$ for some $d\ge 1$?

I expect the answer to be "no" in both cases. Is it known?

Improve this question
$\endgroup$
11
  • $\begingroup$ wouldn't it make more sense to improve your previous question, by making it more precise, rather than ask a new one? $\endgroup$
    – Carlo Beenakker
    Aug 5, 2018 at 19:19
  • $\begingroup$ The previous version also makes sense. There may be different characterizations, not involving the notion of "constructible". $\endgroup$
    – user6976
    Aug 5, 2018 at 19:23
  • $\begingroup$ Could you clarify what constructible means for the case where no strings of that length or smaller are accepted? In this case, $T_M$ would seem to be a partial function. For example, perhaps all strings in the language have length at least $17$. In this case it would seem that $T_M(5)$ is either undefined or infinite, but I am less clear what you mean by constructible in this case. $\endgroup$
    – Joel David Hamkins
    Aug 5, 2018 at 19:23
  • $\begingroup$ @JoelDavidHamkins: The functions are usually considered asymptotically that is the first few values are ignored (or $n\gg 1$). Alternatively, we can assume that these values are $\infty$. Of course if the machine accepts the empty language, its time function is empty but that is not an interesting case. $\endgroup$
    – user6976
    Aug 5, 2018 at 19:26
  • $\begingroup$ You say $M$ is non-deterministic, but I guess you intend that there are no non-halting computations of $M$ on any input? This would be like the usual NP situation, where on any input pair $(u,w)$, where $W$ is a possible witnesses for $u$, you get a yes-or-no answer in some bounded time, whether that witness is good enough. Is this your context? If not, and if you just use non-deterministic machines as they are often described, then you can code the halting problem into your time function, and it might not be computable at all, let alone constructible. $\endgroup$
    – Joel David Hamkins
    Aug 5, 2018 at 19:35

2 Answers 2

Reset to default
3
$\begingroup$

The way you have set up the question, the answer is negative, even for deterministic machines.

To see this, let $L$ be the halting problem, consisting of strings $u$ describing a Turing machine, which halts when started on an empty tape.

This language is recognized by a Turing machine $M$, which on input $u$ simply simulates the computation of that program on an empty tape, and accepts $u$ if this simulation halts. In other words, $u$ is in the language if and only if $u$ is accepted by some computation of $M$, which is what you requested.

For $u$ that are accepted, the time complexity $T_M(u)$ is at least as large as the length of the computation of $u$ on the empty tape, since the simulation takes at least as long as the real thing. Thus, $T_M(n)$ is at least as large as the busy beaver function, since the number of states of the machine coded by a string $u$ is at most the length of $u$. This function is therefore not computable at all, let alone constructible.

As I mentioned in my comment, however, one can avoid this kind of example if you insist that $M$ halts on all input, so that time complexity of $T_M(u)$ is defined not just for acceptable $u$ but also for unacceptable $u$. In this case, you can definitely compute $T_M(u)$ just by running it on all the input, and use this to take the max. But that wouldn't be constructible, which is why I thought maybe this is what you might actually have been interested in. But your reply to my comment says otherwise...

Improve this answer
$\endgroup$
5
  • $\begingroup$ I wonder whether one might be able to modify the argument to a relativized halting problem, using time bounds for the halting problem, and thereby make a counterexample of the type desired. $\endgroup$
    – Joel David Hamkins
    Aug 5, 2018 at 20:11
  • $\begingroup$ I have modified the question, trying to avoid the obstruction that you noticed. With that modification, I think the time function of a deterministic TM is constructible. $\endgroup$
    – user6976
    Aug 5, 2018 at 20:33
  • $\begingroup$ Your question is (almost?) equivalent to asking whether for a given $n$, there is $u$ of length $n$ for which the non-deterministic $M$ takes time $\ge t$. This is a decision question, where the (main) input $n$ is in unary. Unary languages (denoted $TALLY$) cannot be NP-complete, and what you're looking for seems to be a deterministic time bound for $TALLY\cap NP$, or rather, for $TALLY\cap NTIME(n^k)$. I would ask this on cstheory.SE. $\endgroup$
    – domotorp
    Aug 6, 2018 at 8:41
  • $\begingroup$ @domotorp: Thank you! IIt would be easier for me to understand your comment if you convert it to an answer with references. For example, why TALLY cannot be NP-complete? $\endgroup$
    – user6976
    Aug 6, 2018 at 11:05
  • $\begingroup$ Oops, and now I see that I've commented on this answer instead of the original question - sorry! $\endgroup$
    – domotorp
    Aug 6, 2018 at 19:53
0
$\begingroup$

Your question is (almost?) equivalent to asking whether for a given $n$, there is $u$ of length $n$ for which the non-deterministic $M$ takes time $\ge t$. This is a decision question, where the (main) input $n$ is in unary. Unary languages (denoted $TALLY$) cannot be $NP$-complete, and what you're looking for seems to be a deterministic time bound for $TALLY\cap NP$, or rather, for $TALLY \cap NTIME(n^k)$. I would recommend asking this on cstheory.SE

Improve this answer
$\endgroup$

Your Answer

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