# Reductions between languages of different densities?

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 and also Regan and Vollmer 1997). 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.) 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.

• 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 Mar 18 '17 at 20:30
• 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 Mar 19 '17 at 0:01

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.
• 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 Mar 20 '17 at 15:23