Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer
1  
The core point is that NP-hardness is a lower bound while PSPACE-ness is an upper bound. –  Raphael May 3 at 9:36

Your Answer

 
discard

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.