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

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

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

## 2 Answers

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.

• @rus9384 , I don't see how that would follow from the line of logic in my answer. Can you expand? – JoshuaZ Aug 8 '20 at 20:50

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