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

<p>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&#39;_{n + m} = \{x0^m | x \in L_n\}$. In general, $m$ will be some function of $n$, so this might not define $L&#39;$ for all sizes, since we are worried only about the upper density, just make $L&#39;_k = \emptyset$ if $k \neq n + m$. What is the upper density of $L&#39;$? Well, we have </p>

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

<p>Now lets use LOG-reductions to build a machine $M$ for $L$ using a machine $M&#39;$ for $L&#39;$. 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.</p>

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

CC BY-SA 3.0
2011-09-12T13:26:48.173Z
Thanks, this answers the question.  This argument seems to rely on $m$ being polynomially related to $n$ -- would upper density $1/\log n$ be achievable?
András Salamon
CC BY-SA 3.0
2011-09-12T15:15:09.887Z
I think so, you would just need m = log log n. In general for m = f(n) you can pick any f which is in LOG-space (with n in unary). (or NC if you prefer those reductions).
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-11T12:28:54.313Z
2011-09-11T12:28:54.313Z
Artem Kaznatcheev
<p>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 <em>upper density</em> $d(n)$ if $L_n \le 2^n d(n)$ for all sufficiently large $n$.</p>

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

<h2>Motivation</h2>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p><a href="http://dx.doi.org/10.1006/jcss.1998.1615" rel="nofollow noreferrer">Jin-Yi Cai and D. Sivakumar</a> 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.</p></li>
<li><p>By a simple inequality (see e.g. Corollary 2 of <a href="http://projecteuclid.org/euclid.ijm/1255631807" rel="nofollow noreferrer">Rosser and Schoenfeld 1962</a>), PRIMES has upper density $(\log_2 e)/n$.  Question <a href="https://cstheory.stackexchange.com/q/8000">Are the problems PRIMES, FACTORING known to be P-hard?</a> discusses whether PRIMES is P-hard (this seems to be open currently).</p></li>
<li><p>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.</p></li>
</ol>

<p>The work on <a href="http://en.wikipedia.org/wiki/Low_%28complexity%29" rel="nofollow noreferrer">lowness</a> by Fortnow, Hemaspaandra, and others is also possibly related.</p>

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

<h3>Acknowledgements</h3>

<p>See also related question <a href="https://cstheory.stackexchange.com/q/5407">Conditional density of primes</a>.  Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.</p>

CC BY-SA 3.0
2011-09-11T12:49:13.757Z
I think $2^n/n$ (or another polynomial fraction) has too many strings, the better question is to ask about upper and lowerbounds.
Kaveh
<cc.complexity-theory><reference-request><p-hardness>
Density of P-complete languages
András Salamon
# Density of P-complete languages

(Asked by: username_0 on 2011-09-09)

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](http://dx.doi.org/10.1006/jcss.1998.1615) 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](http://projecteuclid.org/euclid.ijm/1255631807)), PRIMES has upper density $(\log\_2 e)/n$. Question [Are the problems PRIMES, FACTORING known to be P-hard?](https://cstheory.stackexchange.com/q/8000) 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](http://en.wikipedia.org/wiki/Low_%28complexity%29) 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](https://cstheory.stackexchange.com/q/5407). Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.

**Tags:** cc.complexity-theory, reference-request, p-hardness
> **Comments:**
> **username_1**: I think $2^n/n$ (or another polynomial fraction) has too many strings, the better question is to ask about upper and lowerbounds.  

---

## 1 answers

### Answer by username_2 on 2011-09-11. Score: 6 | Accepted answer

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)$.

> **Comments:**
> **username_0**: Thanks, this answers the question.  This argument seems to rely on $m$ being polynomially related to $n$ -- would upper density $1/\log n$ be achievable?  
> **username_2**: I think so, you would just need m = log log n. In general for m = f(n) you can pick any f which is in LOG-space (with n in unary). (or NC if you prefer those reductions).  

---

