# Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction.

The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction.

I wonder if NPSPACE is also closed under polynomial-time reduction and/or under log-space reduction.

• What do you think? Have you tried proving that it is closed under such reductions? – Yuval Filmus Aug 30 '17 at 14:17

Closed under polynomial-time: Let $A \leq_P B$ and $B \in NPSPACE$. This means there is a polynomial time computable function $f$ such that $x \in A \iff f(x) \in B$. Using this we can construct a NDTM $N$ which decides $x \in A$ using polynomial space.
N(x)

Since $f$ is computable in polynomial time, it uses at most polynomial space. $B$, too, uses polynomial space, since $B \in NPSPACE$, and so $N$ uses at most polynomial space. This proves that $A \in NPSPACE$.