12
$\begingroup$

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 .

$\endgroup$
27
$\begingroup$

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:

relations between classes

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}$

$\endgroup$
  • 1
    $\begingroup$ Why are EXPSPACE and EXPTIME related? I thought time and space were different resources. One example which comes to mind is breaking a crypto scheme, which would require EXPTIME, but constant space $\endgroup$ – WeCanBeFriends Jun 19 at 22:01
  • 6
    $\begingroup$ The intuitive here is, if you use $f(n)$ space, you must use at least $f(n)$ time, and you shouldn't use more than $2^{f(n)}$ time, because then you must be revisitting the same states. That's why PSPACE $\subseteq $ EXP $\endgroup$ – lox Jun 19 at 22:26
  • $\begingroup$ Is f(n) different to O(n) in your example? $\endgroup$ – WeCanBeFriends Jun 19 at 22:28
  • 1
    $\begingroup$ @WeCanBeFriends One cannot employ exponential time with constant space: you need at least the space used to count until that exponential number (e.g. the program counter of an assembly language), which is polynomial (logarithmic in the exponential) $\endgroup$ – gigabytes Jun 20 at 5:28
  • 4
    $\begingroup$ @gigabytes We don't know that. The best we know is that $P\not = EXPTIME$. $\endgroup$ – Tom van der Zanden Jun 20 at 8:46
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.