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}$?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What is the complexity class called SPARSE? $\endgroup$– nir shaharCommented Aug 8, 2020 at 20:04
-
$\begingroup$ The complexity class containing all sparse languages. $\endgroup$– rus9384Commented Aug 8, 2020 at 20:15
-
$\begingroup$ All unary languages are sparse, so there are undecidable sparse languages. $\endgroup$– ArielCommented Aug 8, 2020 at 20:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ @rus9384 , I don't see how that would follow from the line of logic in my answer. Can you expand? $\endgroup$– JoshuaZCommented Aug 8, 2020 at 20:50
$\begingroup$
$\endgroup$
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^*$.