CSC 341 (Fall 2021)

Reading: Space Complexity

Space Complexity

Enough about time, now it’s time for spaaaaaaaaaaaaaaaaaace.


Reading Problem (Space for Nothing, Time for Free)

The reading proves that while \(\mathsf{SAT}\) is NP-complete, it only takes a linear amount of space, i.e., it is in PSPACE. Adapt this proof technique to show that \(\mathsf{CLIQUE}\) discussed in the previous chapter is also in PSPACE.