2
$\begingroup$

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.

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

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)
 y = f(x)
 return B(y)
end

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

$\endgroup$
2
$\begingroup$

Savitch's theorem implies that NPSPACE is equal to PSPACE, and so it is closed under polynomial time 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.