5
$\begingroup$

Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed?

Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine in time $O(t(n))$ and space $O(s(n))$. (This is the analog of the class of decision problems $\mathsf{TISP}(t(n), s(n))$.) Classical reductions such as polytime (Karp) reduction or logspace reduction only preserve either time or space, but not both. Therefore my question is whether there exists some known notion of reduction under which $\mathsf{TISP}(t(n), s(n))$ is closed.

Notes.

  1. There may be several answers for different range of time and space bounds. I am mainly interested in fine-grained reductions (that is where $t(n)$ and $s(n)$ are precise bounds), but also for unions like $t(n) = \mathsf{poly(n)}$ or $s(n) = \mathsf{polylog(n)}$ for instance.

  2. For the space bound, I am mostly interested in the case $s(n) \le n$ (or even $s(n)\ll n$).

  3. I am also interested in reductions for the classes of decision-problems $\mathsf{TISP}(t(n), s(n))$ if they have been studied.

  4. Of course, my requirements are enough to characterize the reduction I want. My question is really whether this kind of reduction has been studied in the literature, and to have pointers in such case. My impression is that the simultaneous time and space bounds imply that the reduction is necessary an oracle reduction. Indeed, it seems out of question to have a many-one reduction: If we take the input $x$ of a problem $A$ and compute an input $y$ to a problem $B$, the composition of the reduction with the algorithm for $B$ has no reason to run in time $t(n)$ and space $s(n)$: Either we compute $y$ before applying the algorithm for $B$ but the space may be larger than $s(n)$, or we compute the bits of $y$ when needed but the time increases... At least, this is not possible for fine-grained complexity bounds.

Remark. The space-complexity of an algorithm computing a function can be defined using multi-tape Turing machines: The machine has a read-only input tape, a write-once output tape, and a finite number of work tapes; The space complexity is the number of cells of the work tapes that are used during the computation.

$\endgroup$
  • 1
    $\begingroup$ If I understand correctly, the problem with what you propose is that if the algorithm for $g$ has space complexity $s(n)$, you get an algorithm for $f$ that has space complexity $n + s(n)$: Indeed, you first need to write the input to $g$ and then apply the algorithm for $g$. Am I mistaken? $\endgroup$ – Bruno Jun 5 '18 at 14:04
  • 1
    $\begingroup$ Right, I had this proof in mind, and now I notice that what I need is more. Actually, I'd like the reduction to be also time-preserving: Let say I want the algorithm for $f$ to also have time-complexity $O(t(n))$ where $t(n)$ is the time complexity of $g$. Anyway thanks for your comments, they helped me to have a clearer view of what I need. I'll edit my question. $\endgroup$ – Bruno Jun 5 '18 at 14:50

Your Answer

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

Browse other questions tagged or ask your own question.