<p>Let $A$ be any language <em>not in</em> $L$, such that $A$ has density $2^{o(n)}$, and define 
$$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$$
Here $\circ$ is concatenation. The language $B$ has density $\Omega(2^n)$, which is superpolynomial in $2^{o(n)}$. On the other hand, $A$ and $B$ log-space reduce to each other ($A$ to $B$ by concatenating $0$, and $B$ to $A$ by reducing all strings ending in $1$ to the smallest yes instance of A, and removing the last bit from all strings ending in $0$). Hence $B \notin L$ as well.</p>

CC BY-SA 3.0
2017-03-20T15:23:17.880Z
To satisfy the requirement that $B \not\in \textsf{L}$, $A$ should be sufficiently hard in this construction.  It is sufficient to let $A$ be a unary version of Halting which has at most one instance of each input size.
András Salamon
CC BY-SA 3.0
2017-03-20T15:36:53.600Z
@András Salamon, thanks for pointing that out, edited the answer to capture the comment.
daniello
CC BY-SA 3.0
2017-03-19T20:32:02.953Z
2017-03-20T15:33:13.980Z
2017-03-20T15:33:13.980Z
daniello
<p>The <em>density</em> of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ many-one logspace reduces to $B$, and $B$ is not in $\textsf{L} = \text{DSPACE}(\log n)$.
Functions $f,g \colon\mathbb{N} \to \mathbb{N}$ are <em>polynomially related</em> if there are polynomials $p$ and $q$ such that for all $n\in \mathbb{N}$, $f(n) \le p(g(n))$ and $g(n) \le q(f(n))$.</p>

<blockquote>
  <p>If the density of $A$ is not polynomially related to the density of $B$, can there be a logspace reduction from $B$ to $A$?</p>
</blockquote>

<hr>

<h2>Background</h2>

<p>I expect the answer is no, but can't currently show this.</p>

<p>Clearly, if $A$ is in $\mathsf{L}$ then there is no logspace reduction from $B$ to $A$.
So there are some examples for which it is possible to provide a definite negative answer.</p>

<p>I first had in mind the case where $B$ is some hard language, and $A$ is obtained by blowing holes in $B$ by taking $A = B\cap G$, for some gap language $G$ which contains all words of length $n \in S_G$ for some set $S_G \subseteq \mathbb{N}$ (see <a href="https://dx.doi.org/10.1016/0304-3975(85)90217-8" rel="noreferrer">Schmidt 1985</a> and also <a href="https://dx.doi.org/10.1016/S0304-3975(96)00288-5" rel="noreferrer">Regan and Vollmer 1997</a>).
This guarantees a trivial reduction from $A$ to $B$.
Gap languages $G$ usually have exponentially increasing gaps between the intervals of sizes in $S_G$.
This ensures that the densities of $A$ and $B$ are not polynomially related.
However, there is no guarantee that blowing holes in a language always gives rise to a language that has too little structure to be the target of a reduction from $B$.
(The term <em>blowing holes</em> is from <a href="https://dx.doi.org/10.1016/S0304-3975(02)00810-1" rel="noreferrer">Downey and Fortnow 2003</a>.)
The difference in densities might be enough to guarantee this, but I don't immediately see how.</p>

<p>Another example is when $B$ is a mixture of a hard language and $A$.
First create a gappy language $A\not\in\mathsf{L}$ by intersecting some language $C \not\in \textsf{L}$ with a gap language $G$.
$A$ will then only contain instances of sizes that are in the intervals of the set of sizes $S_G$ determining the gap language.
Now create $B$ by mixing $A$ with some hard language $D$ in the gaps, by taking the union of $A$ and the intersection of $D$ with the complement of $G$.
If $D$ is hard enough compared to $C$, such as $D$ being $\textsf{2EXPSPACE}$-hard while $C \in \textsf{PSPACE} \setminus \textsf{L}$, then by the space hierarchy theorem there can be no logspace reduction from $D$ to $A$.
It then seems possible to extend this to show that there is no logspace reduction from $B$ to $A$.</p>

<p>This still leaves the situation where $D$ is harder than $C$ but "not too much", for instance take $D$ to be SAT and $C$ to be STCON, or $D$ to be QBF-SAT and $C$ to be SAT.
To get a result, one might have to assume $\mathsf{L} \ne \mathsf{NP}$ for STCON/SAT or $\mathsf{NP} \ne \mathsf{PSPACE}$ for SAT/QBF-SAT, but it is not immediately clear to me how to use these assumptions.</p>

CC BY-SA 3.0
2017-03-18T20:30:25.623Z
What about $A$ is any language of density $2^{o(n)}$ and $B$ consists of all strings whose last bit is 0, union all strings whose last bit is 1 and the first $n-1$ bits is a string in A?
daniello
CC BY-SA 3.0
2017-03-19T00:01:00.147Z
I think daniello's comment answers the question. In general, many-one reductions tell you very little about density, even if you have many-one reductions in both directions. 1-1 reductions, and 1-1 reductions in both directions (or even stronger, p-isomorphisms) give relations between density (viz. the Berman-Hartmanis Isomorphism Conjecture motivating Mahaney's Theorem; in fact, I think BH isomorphism may have been the main motivation for looking at density at all in the first place...)
Joshua Grochow
<cc.complexity-theory><reductions><structural-complexity>
Reductions between languages of different densities?
András Salamon
# Reductions between languages of different densities?

(Asked by: username_0 on 2017-03-18)

The *density* of a language $X$ is a function $d\_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d\_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ many-one logspace reduces to $B$, and $B$ is not in $\textsf{L} = \text{DSPACE}(\log n)$.
Functions $f,g \colon\mathbb{N} \to \mathbb{N}$ are *polynomially related* if there are polynomials $p$ and $q$ such that for all $n\in \mathbb{N}$, $f(n) \le p(g(n))$ and $g(n) \le q(f(n))$.

> If the density of $A$ is not polynomially related to the density of $B$, can there be a logspace reduction from $B$ to $A$?

---

## Background

I expect the answer is no, but can't currently show this.

Clearly, if $A$ is in $\mathsf{L}$ then there is no logspace reduction from $B$ to $A$.
So there are some examples for which it is possible to provide a definite negative answer.

I first had in mind the case where $B$ is some hard language, and $A$ is obtained by blowing holes in $B$ by taking $A = B\cap G$, for some gap language $G$ which contains all words of length $n \in S\_G$ for some set $S\_G \subseteq \mathbb{N}$ (see [Schmidt 1985](https://dx.doi.org/10.1016/0304-3975(85)90217-8) and also [Regan and Vollmer 1997](https://dx.doi.org/10.1016/S0304-3975(96)00288-5)).
This guarantees a trivial reduction from $A$ to $B$.
Gap languages $G$ usually have exponentially increasing gaps between the intervals of sizes in $S\_G$.
This ensures that the densities of $A$ and $B$ are not polynomially related.
However, there is no guarantee that blowing holes in a language always gives rise to a language that has too little structure to be the target of a reduction from $B$.
(The term *blowing holes* is from [Downey and Fortnow 2003](https://dx.doi.org/10.1016/S0304-3975(02)00810-1).)
The difference in densities might be enough to guarantee this, but I don't immediately see how.

Another example is when $B$ is a mixture of a hard language and $A$.
First create a gappy language $A\not\in\mathsf{L}$ by intersecting some language $C \not\in \textsf{L}$ with a gap language $G$.
$A$ will then only contain instances of sizes that are in the intervals of the set of sizes $S\_G$ determining the gap language.
Now create $B$ by mixing $A$ with some hard language $D$ in the gaps, by taking the union of $A$ and the intersection of $D$ with the complement of $G$.
If $D$ is hard enough compared to $C$, such as $D$ being $\textsf{2EXPSPACE}$-hard while $C \in \textsf{PSPACE} \setminus \textsf{L}$, then by the space hierarchy theorem there can be no logspace reduction from $D$ to $A$.
It then seems possible to extend this to show that there is no logspace reduction from $B$ to $A$.

This still leaves the situation where $D$ is harder than $C$ but "not too much", for instance take $D$ to be SAT and $C$ to be STCON, or $D$ to be QBF-SAT and $C$ to be SAT.
To get a result, one might have to assume $\mathsf{L} \ne \mathsf{NP}$ for STCON/SAT or $\mathsf{NP} \ne \mathsf{PSPACE}$ for SAT/QBF-SAT, but it is not immediately clear to me how to use these assumptions.

**Tags:** cc.complexity-theory, reductions, structural-complexity
> **Comments:**
> **username_1**: What about $A$ is any language of density $2^{o(n)}$ and $B$ consists of all strings whose last bit is 0, union all strings whose last bit is 1 and the first $n-1$ bits is a string in A?  
> **username_2**: I think daniello's comment answers the question. In general, many-one reductions tell you very little about density, even if you have many-one reductions in both directions. 1-1 reductions, and 1-1 reductions in both directions (or even stronger, p-isomorphisms) give relations between density (viz. the Berman-Hartmanis Isomorphism Conjecture motivating Mahaney's Theorem; in fact, I think BH isomorphism may have been the main motivation for looking at density at all in the first place...)  

---

## 1 answers

### Answer by username_1 on 2017-03-19. Score: 8 | Accepted answer

Let $A$ be any language *not in* $L$, such that $A$ has density $2^{o(n)}$, and define
$$B = \{s \circ 1 | s \in \{0,1\}^\*\} \cup \{s \circ 0 | s \in A\}.$$
Here $\circ$ is concatenation. The language $B$ has density $\Omega(2^n)$, which is superpolynomial in $2^{o(n)}$. On the other hand, $A$ and $B$ log-space reduce to each other ($A$ to $B$ by concatenating $0$, and $B$ to $A$ by reducing all strings ending in $1$ to the smallest yes instance of A, and removing the last bit from all strings ending in $0$). Hence $B \notin L$ as well.

> **Comments:**
> **username_0**: To satisfy the requirement that $B \not\in \textsf{L}$, $A$ should be sufficiently hard in this construction.  It is sufficient to let $A$ be a unary version of Halting which has at most one instance of each input size.  
> **username_1**: @András Salamon, thanks for pointing that out, edited the answer to capture the comment.  

---

