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$
3
  • $\begingroup$ What is the complexity class called SPARSE? $\endgroup$
    – nir shahar
    Aug 8, 2020 at 20:04
  • $\begingroup$ The complexity class containing all sparse languages. $\endgroup$
    – rus9384
    Aug 8, 2020 at 20:15
  • $\begingroup$ All unary languages are sparse, so there are undecidable sparse languages. $\endgroup$
    – Ariel
    Aug 8, 2020 at 20:41

2 Answers 2

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.

$\endgroup$
1
  • $\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, 2020 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^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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