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$
5
  • $\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$ Jul 21, 2017 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, 2017 at 0:17
  • $\begingroup$ Cool!! Thank you for your clarification. I'm really interested in these kinds of problems. :) $\endgroup$ Jul 22, 2017 at 6:10
  • $\begingroup$ $DTISP(2^n,n)=DSPACE(n)$. So, your second case is trivial. $\endgroup$
    – rus9384
    Sep 23, 2017 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$ Jan 2, 2018 at 23:12

1 Answer 1

6
$\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$
0

Your Answer

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

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