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?


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.

  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 27, 2012 at 21:47
  • $\begingroup$ @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.) $\endgroup$ Jul 28, 2012 at 7:27
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 28, 2012 at 9:48

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


Your Answer

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

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