Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

Question

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially taking exponential time (2^P(n) where P is polynomial).

Moreover, can it be generalised to EXPTIME in general?

The reason I am asking this is that I wrote some programs to solve degenerate cases of an NPC problem, and they can consume very large amounts of RAM for hard instances, and I wonder if there is a better way. For reference see https://fc-solve.shlomifish.org/faq.html .

Answer 1

Generally speaking, the following is true for any algorithm:

1. 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.
2. 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}$

Answer 2

Yes. Here's a sketch of a direct proof.

If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can simulate a single path deterministically in polynomial space.

But we need to simulate all the paths. Well, there is a constant $c$ that depends only on the transition function of $M$ (and not on its input) such that $M$ has at most $c$ nondeterministic choices at any step. That means that there are at most $c^{p(n)}$ different computation paths for any input of length $n$. We can simulate all of these $c^{p(n)}$ paths as follows. First, write out a $p(n)$-digit number in base-$c$ (this takes space $p(n)$ but that's polynomial, so it's OK). Then, simulate the operation of $M$ and, at the $i$th step of the computation, use the $i$th digit of the number to decide which nondeterministic choice to make. If, for example, the $i$th digit is $6$ and there are only four choices that can be made, abandon that simulation and go on to the next one.

So, now, to do the whole simulation, we start by writing out the number $0\dots 0$, simulate that path of $M$, increment the number, simulate the next path, and so on, until we reach the number where every digit is $c-1$. We've now simulated every possible computation path, and we've done it in time about $c^{p(n)}p(n)$, using space about $2p(n)$. That's exponential time and polynomial space, as required.