Super-logspace mapping reducibility

Question

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.

Answer 1

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.)