4
$\begingroup$

The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it will naturally contain PSPACE problems.

However, I was specifically wondering if there were any PSPACE problems that were not in NP-Hard? (from my understanding, implying that they are easier than the hardest problems in NP).

$\endgroup$
4
$\begingroup$

Assuming we use polytime reductions in both, all PSPACE-hard problems are NP-hard, which follows directly from the definition and from the easy fact NP$\subseteq$PSPACE: a languages $L$ is PSPACE-hard if all languages in PSPACE polytime-reduce to $L$. If $L$ is PSPACE-hard then in particular, all languages in NP polytime-reduce to $L$, and so $L$ is also NP-hard.

On the other hand, there are problems in PSPACE which are not NP-hard, for example $\emptyset$ and $\Sigma^*$. If P=NP then all other problems in PSPACE are NP-hard, since every non-trivial language (a language different from $\emptyset,\Sigma^*$) is NP-hard in this case. If P$\neq$NP then every problem in P also belongs to PSPACE and is not NP-hard.

$\endgroup$
  • 1
    $\begingroup$ The core point is that NP-hardness is a lower bound while PSPACE-ness is an upper bound. $\endgroup$ – Raphael May 3 '14 at 9:36
  • 1
    $\begingroup$ I've gone through most of the related questions/answers here on stackexchange and I'm not sure so asking here: are there non-trivial languages outside of NP that are not NP-hard? $\endgroup$ – starflyer Apr 2 '15 at 18:53
  • 1
    $\begingroup$ @starflyer This can only happen if P$\neq$NP. If you make the stronger assumption that NP$\neq$coNP, then any coNP-complete program is an example. I imagine that you can construct an example under the hypothesis P$\neq$NP using diagonalization, as in Ladner's theorem. $\endgroup$ – Yuval Filmus Apr 2 '15 at 19:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.