Tag Info

New answers tagged polynomial-time-reductions

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