Density of P-complete languages

Question

Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$. Let $L_n$ be the number of strings in $L$ with length $n$. For a function $d(n)$ from the positive integers to the positive real numbers, $L$ has upper density $d(n)$ if $L_n \le 2^n d(n)$ for all sufficiently large $n$.

Do any P-complete Boolean languages have upper density $O(1/n)$?

Motivation

1. PARITY has upper density $1/2$. YES (the language of all finite binary strings) has upper density 1. Any finite language has upper density 0.

2. A sparse language $L$ has the property that there is a polynomial $p(n)$ such that $L_n - L_{n-1} \le p(n)$ for all $n$. If $L$ is a sparse language, then $L_n \le p_1(n)$ for a polynomial $p_1$ of degree one greater than that of $p$, so the upper density of $L$ is zero.

3. Jin-Yi Cai and D. Sivakumar showed that a P-complete language cannot be sparse unless P = L (= LOGSPACE). Since P=co-P, any language of which the complement is sparse cannot be P-complete either, unless P=L.

4. By a simple inequality (see e.g. Corollary 2 of Rosser and Schoenfeld 1962), PRIMES has upper density $(\log_2 e)/n$. Question Are the problems PRIMES, FACTORING known to be P-hard? discusses whether PRIMES is P-hard (this seems to be open currently).

5. In some sense, the complete (or universal)languages for a complexity class contain all the structure of the class. So my tentative hypothesis, based on a wild extrapolation of Cai and Sivakumar's result, would be that such languages cannot be too sparse. The usual polynomial bound defining sparse languages seems too restrictive, so I'm asking about a bound that is a little less restrictive.

The work on lowness by Fortnow, Hemaspaandra, and others is also possibly related.

The question can be asked of classes other than P, but I can't recall any results that would allow establishing density of, say, $k$-SAT. Pointers to relevant literature would be most welcome.

Acknowledgements

See also related question Conditional density of primes. Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.

Answer 1

I don't know what the density of common P-complete problems is, but here is a padding argument that shows how to lower any density below $1/n$:

Take your favorite P-complete language $L_n \subseteq \{0,1\}^n$. This language has some density $d(n) \in \omega(1/n)$. Now define $L'_{n + m} = \{x0^m | x \in L_n\}$. In general, $m$ will be some function of $n$, so this might not define $L'$ for all sizes, since we are worried only about the upper density, just make $L'_k = \emptyset$ if $k \neq n + m$. What is the upper density of $L'$? Well, we have

\[ d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m} \]

Now lets use LOG-reductions to build a machine $M$ for $L$ using a machine $M'$ for $L'$. Well, if you are given an input $x$ then simply copy it one bit at a time to the query tape (also use a counter to count what $n$ is), then use a second counter to count upto $m(n)$, adding one every time you add a zero to the query tape (to have log space, we need $m(n) \in poly(n)$ and easily computable). Then query and return the output as your answer.

If we want to be sure we are smaller than $1/n$ then just pick $m(n) = n$, and then we will have $d'(2n) \leq d(n)/2^n \in O(1/n)$.