Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
Generally speaking, the following is true for any algorithm:


Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain nothing by running more than $2^{f(n)}$ time.


It follows that:


  $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$


The statemement is known as part of the relations between the classes, as depicted by the following diagram:



The explanation is simple: a problem $Q$ $\in$ $\mathbf{NP}$ has a polynomial length certificate $y$. An algorithm that tests all possible certificates is an algorithm that decides $Q$ in time $\large 2^{n^{O(1)}}$.

Its space requirement is:


$y$ (polynomial in $n$)
space required to verify $y$. Since $y$ is a polynomial certificate, it can be verified in polynomial time, hence cannot possibly require more than polynomial space.


Since the sum of two polynomials is also a polynomial, $Q$ can be decided with polynomial space.



Example:

Suppose $\varphi$ is an instance of 3-CNF on literals $x_1 \dots x_n$, with $m$ clauses. An assignment $f$ is some function $f:\{x_1\dots x_n\} \rightarrow \{0,1\}$.

It holds that:


There are $2^n$ different assignments.
Given an assignment $f$, it takes $O(m)$ time to calculate the value of $\varphi$, therefore it cannot require more than $O(m)$ space.


So an algorithm $A$ that checks all possible assignments will use polynomial space, run in exponential time and decide 3-SAT.

It follows that:

3-SAT $\in \mathbf{PSPACE}$, and since 3-SAT is NP-Complete, $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$