# If every NP-hard language is PSPACE-hard then NP=PSPACE

To prove PSAPCE = NP we will show following inclusions :

• NP $$\subseteq$$ PSPACE : If every NP-hard language is PSPACE-hard then SAT is also PSPACE-hard. Since every language in PSPACE can be reduced polynomially to PSPACE-hard implies SAT $$\in$$ PSPACE.

SAT $$\in$$ PSPACE.
If L $$\leq_{P}$$ B and B $$\in$$ PSPACE $$\implies$$ L $$\in$$ PSPACE.

• PSPACE $$\subseteq$$ NP : If every NP-hard language is PSPACE-hard, we can then say SAT is PSPACE-hard, now since SAT $$\in$$ NP $$\implies \forall L \in$$ PSPACE $$\leq_{P}$$ SAT $$\implies$$ PSPACE $$\subseteq$$ NP. $$\square$$\

I am unsure about the second item of proof. The confusion is about where I am saying SAT is in PSPACE-hard and also in NP and using that to prove the inclusion. Is the logic correct? If yes, Is there a clearer way to write it?

• Checking proofs for you is beyond the scope of this site. Also, it is not our goal here to make broad advances to science in a single post (see here for a related discussion). Our goal is to build an archive of knowledge, based on high-quality questions and answers, that is likely to be useful to others in the future. It seems unlikely anyone else will have this exact same question in the future.
– D.W.
Jun 12, 2022 at 4:54

"SAT is PSPACE-hard. Since SAT $$\in$$ NP $$\implies \forall L \in$$ PSPACE $$\leq_{P}$$ SAT $$\implies$$ PSPACE $$\subseteq$$ NP" is indeed confusing.
What is much clearer is "SAT is PSPACE-HARD $$\implies (\forall L \in$$ PSPACE, $$L\leq_{P}$$ SAT) $$\implies$$ ($$\forall L \in$$ PSPACE, $$L$$ is in NP) $$\implies$$ (PSPACE $$\subseteq$$ NP)".
"NP $$\subseteq$$ PSPACE" is true, even if "every NP-hard language is PSPACE-hard" is not true. It can be proved directly. Or you can use that fact directly assuming you have learned/been taught it.
Well, the way in which it is proved in the question does not make much sense, especially the implication in this statement, "SAT is also PSPACE-hard. Since every language in PSPACE can be reduced polynomially to PSPACE-hard implies SAT $$\in$$ PSPACE." The fact that "SAT is PSPACE-hard" should not be helpful in proving "SAT $$\in$$ PSPACE".