1
$\begingroup$

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?

$\endgroup$
2
$\begingroup$

The same way that you show that any problem in P is polytime reducible to any other, or that any decidable language is Turing reducible to any other: solve the problem in the reduction.

Note that the claims (yours in the question and mine above) aren't quite true for many-one reductions, since you can't reduce any other language to $\Sigma^*$ or $\emptyset$ using many-one reductions.

$\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.