1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 12, 2022 at 4:54

1 Answer 1

2
$\begingroup$

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

  • The first implication is according to the definition of PSPACE-HARD.
  • The second implication holds since NP is closed under polynomial-time many-one reduction and SAT is in NP.
  • The third implication is a tautology.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.