1
$\begingroup$

A class $C$ is closed under polynomial time reductions if for every two languages $๐ฟ_1 , ๐ฟ_2$ such that $๐ฟ_1 \leq_{๐‘} ๐ฟ_2$ and $๐ฟ_2 \in C$, it holds that $๐ฟ_1 \in C$.

My question is how to prove that PSPACE is closed under polynomial time reductions?

My motivation: PSPACE is closed under polynomial-time reductions because any language $L_1 \leq_p L_2$ means $L_1$ can be decided by a polynomial-time reduction to $L_2$ , and since $L_2 \in \text{PSPACE}$ , $L_1$ can also be decided in PSPACE by simulating both the reduction and the PSPACE algorithm for $L_2$ . PSPACE algorithms can simulate polynomial-time computations with space efficiency.

How to proceed from here? This question asked here before with no answer.

$\endgroup$
3
  • $\begingroup$ A polynomial time algorithm is also a polynomial space algorithm (because each step in the execution of the algorithm consumes exactly one unit of time and at most one unit of space). So a polynomial time reduction is also a reduction in polynomial space. $\endgroup$ Commented Feb 2 at 23:10
  • $\begingroup$ @RobArthan that's I understand but how to prove that? $\endgroup$ Commented Feb 2 at 23:13
  • $\begingroup$ Just work carefully through the definitions of the space and time usage. By induction you can show that the space usage is less than or equal to the time usage, $\endgroup$ Commented Feb 2 at 23:15

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.