PSPACE: The set of problems that can be run on a (regular) Turing Machine using an amount of "extra space" that is polynomial on the length of the input. "Extra space": The number of locations on the tape visited by the TM other than those locations on which the input was written. QBF is in PSPACE. It may or not not be in P. QBF is a PSPACE-complete problem, meaning every problem in PSPACE can be reduced to it, in the same way that NP problems can all be reduced to SAT: every problem in PSPACE can have its input transformed into valid input for QBF, using only polynomial time to do this, such that QBF always gives the same answer as the original problem. SAME DEAL: If any of the PSPACE-complete problems can be solved in polynomial time, then P = PSPACE. But, so far, no one has figured out how to do this. Now, it pretty clear that everything in P is also in PSPACE. If a program runs in polynomial time, it can't visit more than a polynomial number of spaces (because visiting a space uses a time step). Everything in NP is also in PSPACE, and that's a homework problem for you. The state of things right now is that P lies within the intersection of NP and PSPACE and we don't know anything more than that, really. PSPACE is not studied nearly as much as NP. The P=PSPACE is every bit as unsolved as P=NP, but no one cares too much about that. VIRTUAL MEMORY: In ye olden days, your computer had RAM. RAM would bits of information as long as you needed them do, and as long as your computer was powered up. If your program required more memory than you had available, then things got interesting. I had to learn "overlays" when I started serious programming. And your major implemented languages had overlay libraries doing this. Overlay: When your program is too big to fit in your RAM, your program is broken into pieces and when you need a piece that isn't loaded, your program would have to manually load that piece onto a chunk of memory you didn't anticipate needing for a while. Virtual Memory does this at the operating system level. 8-bit addressing, 16-bit addressing, 32-bit addressing, 64-bit addressing, 128-bit addressing. This means that you can identify a specific byte in memory by using 8, 6, 32, 64, or 128 bits. There is no way your RAM can hold 2^64 distinct bytes. This is handled by virtual memory.