10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think $2^n/n$ (or another polynomial fraction) has too many strings, the better question is to ask about upper and lowerbounds. $\endgroup$ – Kaveh Sep 11 '11 at 12:49
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – András Salamon Sep 12 '11 at 13:26
  • 1
    $\begingroup$ 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). $\endgroup$ – Artem Kaznatcheev Sep 12 '11 at 15:15

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.