New answers tagged

2 votes
Accepted

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

"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 ...
user avatar
  • 34k

Top 50 recent answers are included