0
$\begingroup$

A language $L$ is PSpace-complete, if it meets two conditions:

  1. It is in PSpace.
  2. Every other PSpace-complete language reduces to it in polynomial time.

Question: suppose we change the second condition to polynomial space (instead of time)? Why is it so that then SAT would be PSpace-complete?

$\endgroup$
4
$\begingroup$

Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that first decides whether its input $w$ is in $Y$ and then maps to a fixed "yes" instance of $X$ if so, and a fixed "no" instance if not.

Note also that the actual definition of PSPACE-completeness requires that every language in the whole of PSPACE reduces to the complete language. The definition you've given is circular, since it defines PSPACE-completeness in terms of itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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