What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Question

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}$?

Answer 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.

Answer 2

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^*$.