12
$\begingroup$

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}(g(n), O(s(n)))$ relate to $\textrm{DTISP}(f(n), O(s(n)))$ if $\frac{f}{g}$ grows fast enough?

I am especially interested in the case that $s(n) = n$, $g(n) = n^3$ and $f(n) = 2^n$.

In particular, I considered the following language: $ L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps}, $ $ k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \} $

However, $L_k$ could be decided in $n^3$ steps by using $(k+1)n \in O(n)$ space.

Without limiting $M$ to four tape symbols and thus allowing to compress $O(n)$ cells into $n$ cells, we get space issues when simulating an $M$ with too many tape symbols. In this case, the language is not in $\text{DSPACE}(O(n))$ anymore. The same happens when setting $k = h(|w|)$ for some $h$ that can be computed fast enough.

This question is basically a rephrase of my question here.

Edit Summary: Changed $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ to $\textrm{DTISP}(f(n), s(n))$, however, I think the intersection is also worth to think about.

$\endgroup$
  • $\begingroup$ Awesome question!! It's also quite interesting to look at DTISP(g(n), s(n)) vs DTISP(f(n), s(n)) if $\frac{f}{g}$ grows fast enough. DTISP(g(n), s(n)) represents languages that can be solved by a single algorithm that runs in at most g(n) time using s(n) space while DTIME(g(n)) $\cap$ DSPACE(s(n)) represents languages with two algorithms where one algorithm runs in g(n) time and the other algorithm runs in s(n) space. $\endgroup$ – Michael Wehar Jul 21 '17 at 22:49
  • 1
    $\begingroup$ Oops... I actually wrote D-SPACE(O(s(n)))-TIME(g(n)) first, but I didn't like the look of what MathJax made out of it, so I quickly changed it to DSPACE(O(s(n))) ∩ DTIME(g(n)) without thinking much about it. My initial question is about what I wrote first, but the intersection DSPACE(O(s(n))) ∩ DTIME(g(n)) is also very interesting - I am glad I did this mistake. Clearly DTISP(g(n), s(n)) ⊆ DTIME(g(n)) ∩ DSPACE(s(n)). Is this a proper inclusion? According to wikipedia, its properness is unknown for DTISP(P, PolyL) ⊆ DTIME(P) ∩ DSPACE(PolyL): wikiwand.com/en/SC_(complexity) $\endgroup$ – Henning Jul 22 '17 at 0:17
  • $\begingroup$ Cool!! Thank you for your clarification. I'm really interested in these kinds of problems. :) $\endgroup$ – Michael Wehar Jul 22 '17 at 6:10
  • $\begingroup$ $DTISP(2^n,n)=DSPACE(n)$. So, your second case is trivial. $\endgroup$ – rus9384 Sep 23 '17 at 19:59
  • $\begingroup$ It's worth mentioning that a time hierarchy for a fixed amount of space can be obtained for Turing machines with $k$ tapes for fixed $k$ by using arguments similar to Hopcroft-Paul-Valiant and tight time hierarchies for $k$-tape machines. See e.g. W.J. Paul. `On time hierarchies' in STOC’77 $\endgroup$ – Sam McGuire Jan 2 '18 at 23:12
5
$\begingroup$

This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$.

However, under plausible computational complexity conjectures, there is a proper hierarchy. For example, if for every $ε>0$, CIRCUIT-SAT ∉ i.o.-$O(2^{n-ε})$, then $\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
where $f(n)≥n$, $f(n)$ is $2^{o(\min(n,s(n)))}$, and $f$ is time-space constructible.

In particular (under the hypothesis), existence of a satisfying assignment for circuits with $⌊\mathrm{lg}(f^{1+ε/2})⌋$ inputs and size $(\log f)^{O(1)}$ serves as a counterexample to the equality of the classes.

Notes:

  • CIRCUIT-SAT is at least as hard as $k$-SAT (which is used in the strong exponential time hypothesis).

  • Per convention, in CIRCUIT-SAT, $n$ is the number of input wires; circuit size is $n^{O(1)}$.

  • If the assumption used CIRCUIT-SAT for quasilinear circuit sizes, then the bound on $f(n)$ can be relaxed to $O((2-ε)^{\min(n,s(n))})$. Also, weaker/stronger assumptions on hardness of CIRCUIT-SAT give weaker/stronger hierarchies (that we can currently prove).

  • i.o. means infinitely often, and can be dropped for $f$ that are in a certain sense continuous (including $f(n)=n^a$).

  • It appears likely that the DTISP hierarchy is sharp enough to distinguish $O(f)$ from $o(f/\log f)$ (and perhaps $o(f)$) (when $f$ is not too large relative to the permitted space).

  • To distinguish $n^a$ from $2^n$, we only need the weaker assumption P≠PSPACE.

$\endgroup$

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.