We have focused so far on time constraints, what about memory constraints?

PSPACE is the set of problems that can be solved by an algorithm using a polynomial amount of memory (space). In polynomial time, an algorithm can only use a polynomial amount of space, $\text{P} \subseteq \text{PSPACE}$

Lemma: $\text{3-SAT} \in \text{PSPACE}$

Proof: Each n-string $x_1, \dots, x_n$ stores a T/F assignment i.e. $x_i = 1 \rightarrow \text{True}$

Star from the 00…000 string, check if this assignment satisfies all the clauses. If YES then we’re done, we’ve found a satisfying assignment. Otherwise, add 1 to the string and test the next assignment.

At any point in time, we only store one string (all the clauses). i.e. a polynomial amount of space.

Note: This alg. takes an exponential amount of time as it “counts” from 0 to $2^n-1$, but this is allowed.

Theorem: $NP \subseteq \text{PSPACE}$

Proof: Take a problem Q in NP. There is a polynomial reduction $Q \rightarrow 3Sat$ and 3-SAT is NP-Complete. This reduction using a poly amount of space. We can solve 3-SAT in polynomial space so we can solve Q in polynomial space too.

So $Q \in \text{PSPACE}$

If Q is in PSPACE, then so is the complement ${\bar Q}$. [x is YES instance of Q relates to x is NO instance of ${\bar Q}$. So $\text{coNP} \subseteq \text{PSPACE}$.

Open Problem $P \not= \text{PSPACE}$, we can’t prove this yet.

But we can determine the hardest problems in PSPACE . A problem Q is PSPACE-complete if: (1) $Q \in \text{PSPACE}$ and (2) Every problem $R \in \text{PSPACE}$ has a polyspace reduction $R \rightarrow Q$

QSAT allows us to use universal quantifiers as well as existential quantifiers.

Why is QSAT in PSPACE?

I missed the rest of this lecture… woops.

Written on November 25, 2014