6
$\begingroup$

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$. The smallest time of such a computation is denoted $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$.

Question. Can one characterize all time functions of non-deterministic Turing machines, say, in terms of the time complexity of computing their values?

Update Time functions of deterministic Turing machines are time-constructible. Since there is an exponential slowdiown when going from non-deterministic to deterministic TM, there is a similar restriction for non-deterministic time function. The question is: what is the "correct" restriction.

Improve this question
$\endgroup$
7
  • $\begingroup$ I guess this question is most interesting when $L$ is recognizable, but it's complement is not (so $L$ is not computable). In this case $T_M(n)$ will not have a computable upper bound. In this case, the choice of non-deterministic versus deterministic Turing machines doesn't matter so much, since it's just an exponential slowdown to move from non-deterministic to deterministic Turing machines, which is nothing compared to the growth rate of $T_M(n)$. However, we should be able to get an upper-bound on the growth rate of $T_M(n)$: it must have an upper-bound computable in the halting set. $\endgroup$
    – James
    Commented Aug 1, 2018 at 6:41
  • $\begingroup$ @James: I do not need examples, I need a characterization of the class of functions. $\endgroup$
    – user6976
    Commented Aug 1, 2018 at 7:24
  • $\begingroup$ I need a characterization in the form: $f$ belongs to the class (at least asymptotically) iff there exits a Turing machine computing the values $f(n)$ in time ... The most interesting functions in that class - all. $\endgroup$
    – user6976
    Commented Aug 1, 2018 at 8:03
  • 1
    $\begingroup$ I'm also a little bit confused, but can you perhaps explain in more detail exactly what kind of result you're expecting? In particular, it's certainly the case that essentially all computable $f()$ (at least those with $f(n)\geq n$) are in the class, which seems to make any questions about the time needed to compute $f()$ largely moot? $\endgroup$
    – Steven Stadnicki
    Commented Aug 3, 2018 at 4:21
  • $\begingroup$ @StevenStadnicki: It is not true that essentially all computable functions are in the class. The time function $T(n) $ is computable in time at most $T(n)$ non-deterministically: run the TM and a counting TM in parallel (the second TM counts the steps of the first TM). $\endgroup$
    – user6976
    Commented Aug 3, 2018 at 10:20

1 Answer 1

Reset to default
-3
$\begingroup$

Not clear what you're asking, but normally we define complexity classes in terms of asymptotics of N, i.e. log(N), poly(N), exp(N), 2exp(N), etc. That the TM is nondeterministic doesn't change the overall picture much, though it's unknown what cases it changes the class of languages recognizable (the P vs NP problem is an example of this). See also:

https://en.wikipedia.org/wiki/Time_hierarchy_theorem

Maybe you want: https://cstheory.stackexchange.com/

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I have explained what I need in my comments. $\endgroup$
    – user6976
    Commented Aug 3, 2018 at 10:15

You must log in to answer this question.