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$?


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.

  • 4
    $\begingroup$ 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? $\endgroup$
    – daniello
    Mar 18 '17 at 20:30
  • 2
    $\begingroup$ 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...) $\endgroup$ 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.

  • $\begingroup$ 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. $\endgroup$ Mar 20 '17 at 15:23
  • $\begingroup$ @András Salamon, thanks for pointing that out, edited the answer to capture the comment. $\endgroup$
    – daniello
    Mar 20 '17 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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