Question 1: Is it possible to create an algorithm for deterministic Turing machine that will run not in P neither EXPTIME?

Question 2: For me it seems that the answer for my question is it is impossible. If my reasoning is correct, it means that any function that describes complexity will have polynomial(x) or 2^polynomial(x) form.

Does my reasoning is correct?

  • $\begingroup$ What reasoning? $\endgroup$ – Yuval Filmus Oct 23 '18 at 20:53
  • $\begingroup$ Does this comment is useful? (hint, grammar is important.) $\endgroup$ – John L. Oct 24 '18 at 0:19

A function $f(n)$ is time-constructible if there is a Turing machine that runs in time exactly $f(n)$, where $n$ is the input size (in bits). Kobayashi, in his paper On proving time constructibility of functions, showed that if $f(n)$ can be computed in time $O(f(n))$ then $f(n)$ is time-constructible. In particular, functions like $n^{\lfloor \log_2 n \rfloor}$ are time-constructible, even though they lie strictly between polynomial time and exponential time.

In fact, the time hierarchy theorem even shows that there are some decision problems which can be computed in time $O(n^{\log n})$ but not in polynomial time. This shows that there are problem not in $\mathsf{P}$ which can be computed in faster than exponential time.

| cite | improve this answer | |
  • 1
    $\begingroup$ Adding to this, the same hierarchy theorem lets us construct problems with optimal running time roughly $O(2^{2^{2^n}})$ (or worse), which is neither polynomial nor 2^polynomial. $\endgroup$ – Yonatan N Oct 24 '18 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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