# What is the smallest time/space complexity class for which no sparse language is hard?

For example, whether there exists $$\mathsf{PSPACE}$$-hard sparse language an open problem, as it is not yet known whether polynomial hierarchy collapses.

But is it a solved problem for larger complexity classes like $$\mathsf{EXP}$$ or $$\mathsf{PR}$$? What is the smallest complexity class (that is larger than $$\mathsf{PSPACE}$$) for which it is a solved problem?

• I think any class bigger than pspace that has complete sets has the property that you want. for example, exp has no sparse complete sets. suppose for contradiction pspace has a sparse-complete set then pspace is in p/poly so pspace=ma. on the other side there is np-complete sparse language so np=p=ph. so p=exp. and it contradicts with time hierarchy theorem. I think it works for any complexity bigger than pspace. with the same proof. – Mohsen Ghorbani Oct 4 '20 at 19:37
• @MohsenGhorbani, apparently it also is possible to prove P != PSPACE the same way, but I am not sure. Still, the theorem explaining what happens if there is PSPACE sparse language exists. Maybe it'd be possible to prove PSPACE != NEXP similar way. – rus9384 Oct 4 '20 at 19:45
• Although, my point is, whether there would be sparse languages between EXP and NEXP and so on. They still would be EXP-hard. – rus9384 Oct 4 '20 at 20:05
• no, it does not work for p vs pspace with this technique. The Mahaney's theorem states that if there is sparse np-hard language then np=p. If there is sparse pspace-hard language then $pspace \subset p/poly$ so the polynomial hierarchy collapses to $\Sigma_2$ so p = pspace. It is not possible to prove pspace!=nexp with this kind of techniques because of algebraization barier. – Mohsen Ghorbani Oct 4 '20 at 21:03
• If you prove NEXP != EXP we can create a sparse language in NEXP\EXP and they are not EXP-hard. – Mohsen Ghorbani Oct 4 '20 at 21:05