<p>In <a href="http://www.springerlink.com/content/g5005673824gg68n/?CFID=133785327&amp;CFTOKEN=38362984&amp;MUD=MP" rel="nofollow">Model Checking Recursive Programs with Numeric Data Types</a>, Hague and Lin presented a NEXP-complete language under logspace reduction, called $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ composed by strings </p>

<p>\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.</p>

<p>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 $.</p>

<ul>
<li>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.</li>
<li>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.</li>
</ul>

<hr>

<p>It is not hard to show that $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ can be reduced to NP-Complete $ \mathtt{KNAPSCAK} $ via <strong>linearspace reduction</strong>.</p>

<p>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 <strong>polyspace reducible</strong> 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.)</p>

CC BY-SA 3.0
2012-07-30T15:05:36.097Z
2012-07-30T15:05:36.097Z
Abuzer Yakaryilmaz
<p>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. </p>

<p>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.</p>

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

<hr>

<p>DEFINITION</p>

<p>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 </p>

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

<p>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.</p>

<hr>

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

CC BY-SA 3.0
2012-07-27T21:47:07.680Z
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
CC BY-SA 3.0
2012-07-28T07:27:54.030Z
@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
CC BY-SA 3.0
2012-07-28T09:48:49.460Z
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
<cc.complexity-theory><reference-request><reductions><space-bounded>
Super-logspace mapping reducibility
Abuzer Yakaryilmaz
# Super-logspace mapping reducibility

(Asked by: username_0 on 2012-07-27)

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.

**Tags:** cc.complexity-theory, reference-request, reductions, space-bounded

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: 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.)  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2012-07-30. Score: 1 | Accepted answer

In [Model Checking Recursive Programs with Numeric Data Types](http://www.springerlink.com/content/g5005673824gg68n/?CFID=133785327&CFTOKEN=38362984&MUD=MP), 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.)


---

