0
$\begingroup$

I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked my instructor whether any problem, as long as it uses polynomial space to solve, is in PSPACE, and the instructor said yes! This makes me wonder if problems like the two-sum problem are in PSPACE, since you can solve two-sum using polynomial space?

$\endgroup$

1 Answer 1

1
$\begingroup$

As you said yourself: The definition of PSPACE is all problems that can be solved using polynomial space. Therefore, if a problem can be solved using polynomial space, then it is in PSPACE.

PSPACE is a very large class of problems, and it contains pretty much every problem you will ever come across.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. $\endgroup$ Mar 14 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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