# Super-logspace mapping reducibility

There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to use more space (super-logspace), then the length of the output string can be super-polynomial.

Therefore, it seems interesting to me to ask whether this blow-up helps us to reduce some difficult problems to some easier problems when using super-logspace $\left(\omega(\log n) \right)$. I am not interested in the "cheap" tricks such as padding.

More generally, is there any literature on super-logspace (or super-polynomial) mapping reducibility?

DEFINITION

Language $\mathtt{A}$ is $s(n)$-space mapping reducible to language $\mathtt{B}$, shown as $\mathtt{A} \le_{m}^{s} \mathtt{B}$, if there exists a $s(n)$-space DTM $\mathcal{D}$ outputting $f_{\mathcal{D}} (w)$ for a given input $w$ such that

\begin{equation*} w \in \mathtt{A} \mbox{ if and only if } f_{\mathcal{D}} (w) \in \mathtt{B}, \end{equation*}

where $\mathcal{D}$ has a two-way read-only input tape, a two-way read/write work tape, and a one-way write-only output tape.

UPDATE: I have found an answer to my own question. But, I am still interested in further results.

• you don't need padding, even outputting a super polynomial string is not possible using poly-bounded functions. You may want to check PSpaceF and FPSpace. Generally CF classes are not studied that much because of this issue (e.g. unlike P vs. PSpace and FP vs. FPSpace, it is easy to separate PSpaceF from PF) and the corresponding poly-bounded classes FC are preferred. – Kaveh Jul 27 '12 at 21:47
• @Kaveh: Thank you for your comment! What is the difference between PSpaceF and FPSpace? (Unfortunately, I ran into the same definition for both of them after googling.) – Abuzer Yakaryilmaz Jul 28 '12 at 7:27
• The output of CF classes do not need to be polynomialy-bounded so for example a function in PSpaceF can output an exponentially long string while a function in FPSpace cannot. – Kaveh Jul 28 '12 at 9:48

In Model Checking Recursive Programs with Numeric Data Types, Hague and Lin presented a NEXP-complete language under logspace reduction, called $\mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK}$ composed by strings
\begin{equation*} a^m \# a^k \# \theta, \end{equation*} where $\theta$ is a Boolean formula with variables $x_1, \ldots, x_{m+k}$ satisfying that the string $b \# a_1 \# \cdots \# a_{2^k-1}$ defined based on $\theta$ (described below) is a member of $\mathtt{KNAPSCAK}$, i.e. $\sum_{i=1}^{2^k-1} a_i z_i = b$ for some $z_1, \ldots,z_{2^k-1} \in \{0,1\}$, where $b$ and each $a_i$ are precisely $2^m$ bits (leading 0s permitted) binary numbers.
The string $b \# a_1 \# \cdots \# a_{2^k-1}$ is defined based on $\theta$ as follows. Let $(i)_{2,k}$ be the $k$-bit binary representation of $i$.
• The $i^{th}$ bit of $b$ is the value of $\theta$ by setting $x_1,\ldots,x_{k+m}$ to the digits of $0^k (i)_{2,m}$ in order.
• The $i^{th}$ bit of $a_j$ is the value of $\theta$ by setting $x_1,\ldots,x_{k+m}$ to the digits of $(j)_{2,k} (i)_{2,m}$ in order.
It is not hard to show that $\mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK}$ can be reduced to NP-Complete $\mathtt{KNAPSCAK}$ via linearspace reduction.
Moreover, since any language in NEXP is logspace reducible to $\mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK}$, we can say that any language in NEXP is polyspace reducible to $\mathtt{KNAPSACK}$. (Here we can combine logspace and linearspace reductions. Since the output string after logspace reduction can have polynomial length, we can use polynomial space overall.)