Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
The core point is that NP-hardness is a lower bound while PSPACE-ness is an upper bound. – Raphael May 3 '14 at 9:36
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? – starflyer Apr 2 '15 at 18:53
@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. – Yuval Filmus Apr 2 '15 at 19:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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