Return to 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$. 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?

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.

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?

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?