Question

Question:Show that if every NP-hard language is also PSPACE-hard, then PSPACE = NP.

Short answer

.

Step-by-step solution

Step-1: NP-Hard and PSPACE

The NP problems are a class of problems whose solutions are difficult to find but simple to prove, and which are solved in polynomial time by a Non-Deterministic Machine.A problem is NP-hard if all problems in NP can be reduced to it in polynomial time, even if it isn't in NP.

PSPACE is the collection of all decision problems that a Turing machine can answer using a polynomial space in computational complexity theory.

 Step-2: the explanantion of PSPACE-hard

If every NP-hard language is also PSPACE-hard, then SAT is also PSPACE-hard, and every PSPACE language can be reduced to SAT in polynomial time. As a result,$\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{\subseteq }\mathit{N}\mathit{P}$because $\mathit{S}\mathit{A}\mathit{T}\mathbf{\in }\mathit{N}\mathit{P}$and therefore$\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{=}\mathit{N}\mathit{P}$because we know.$\mathit{N}\mathit{P}\mathbf{\subseteq }\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$