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?

  • $\begingroup$ 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. $\endgroup$ – Mohsen Ghorbani Oct 4 '20 at 19:37
  • $\begingroup$ @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. $\endgroup$ – rus9384 Oct 4 '20 at 19:45
  • $\begingroup$ Although, my point is, whether there would be sparse languages between EXP and NEXP and so on. They still would be EXP-hard. $\endgroup$ – rus9384 Oct 4 '20 at 20:05
  • $\begingroup$ 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. $\endgroup$ – Mohsen Ghorbani Oct 4 '20 at 21:03
  • $\begingroup$ If you prove NEXP != EXP we can create a sparse language in NEXP\EXP and they are not EXP-hard. $\endgroup$ – Mohsen Ghorbani Oct 4 '20 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.