1
$\begingroup$

Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity class $\mathsf{SPARSE}$?

$\endgroup$
  • $\begingroup$ What is the complexity class called SPARSE? $\endgroup$ – nir shahar Aug 8 at 20:04
  • $\begingroup$ The complexity class containing all sparse languages. $\endgroup$ – rus9384 Aug 8 at 20:15
  • $\begingroup$ All unary languages are sparse, so there are undecidable sparse languages. $\endgroup$ – Ariel Aug 8 at 20:41
1
$\begingroup$

If by SPARSE you mean the set of languages where the acceptance occurs on a set of zero density, then it is not in EXP or EXPSPACE. It isn't even computable. To see this, pick your favorite computable enumeration of Turing machines T_n, and consider the language L in the alphabet {0,1} where a string S is in L if and only if L is consists just of n 1s, and where T_n halts on the blank tape. Since the problem of whether a given Turing machine halts on the blank tape is undecidable (if one can do it, one can solve the Halting Problem), our language L is undecidable. Using this same trick with a padding argument we can make languages which are as sparse as we want but are not computable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @rus9384 , I don't see how that would follow from the line of logic in my answer. Can you expand? $\endgroup$ – JoshuaZ Aug 8 at 20:50
0
$\begingroup$

I'm not sure if it's the smallest class, but the natural candidate is $P/poly$ - for each $n$, the "advice" can just encode all acceptable strings of length $n$ (by definition of $SPARSE$, their number is polynomial).

$P/poly$ is also a strict superset of $SPARSE$: for example, it contains $\Sigma^*$.

| cite | improve this answer | |
$\endgroup$

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.