1
$\begingroup$

The proof (one of the standard ones, anyway) for Cook-Levin uses snapshots. E.g., see Cook-Levin proof (end of page 2, early page 3)

Now, $z_i$ ( where $z_i$ describes a snapshot of the machine ) depends on $z_{i-1}$ and $z_{prev_{m}(i)}$, but to calculate $z_i$ we cannot erase index $i$, or we will forget what we are currently calculating. What happens if we are restricted to logspace? If we keep the recursive procedure, the stack may well take more than logspace since the variable i might become very large.

And a follow up is, if such log space reduction really exists, wouldn't that imply $P$ is in $L$?

$\endgroup$
3
  • 1
    $\begingroup$ please include the problem description in addition to the link. $\endgroup$
    – sashas
    Mar 4 '16 at 17:40
  • 1
    $\begingroup$ Also you should briefly explain the notations you are using. $\endgroup$
    – sashas
    Mar 4 '16 at 17:50
  • $\begingroup$ If "we are restricted to logspace", then we should use a sensible reduction, rather than that paper's "proof of the Cook-Levin Theorem." ​ ​ $\endgroup$
    – user12859
    Mar 4 '16 at 17:59
3
$\begingroup$

To address your "follow-up", no. The ability to use logspace reductions instead of polynomial time reductions to prove NP-completeness doesn't prove that P is contained in L. It just proves that you don't need the full power of polynomial time reductions to define NP-completeness. The situation is similar to saying, "Hey, there are lots of polynomial-time algorithms for graph reachability but I just found out that the problem is in logspace. Does that mean that P$\,=\,$L?" except that now we're talking about a whole class of computations (the reductions) rather than just one problem.

In fact, if you check out books on descriptive complexity,1 you'll see that we can use even weaker notions of reduction (reductions definable by first-order formulas) and still define a meaningful and, as far as we know, equivalent notion of NP-completeness. This is reassuring: it tells us that NP-completeness is a robust concept that doesn't seem to depend exactly on how you define it.

I say "doesn't seem to depend" because, as far as I'm aware, it is not known that defining NP-completeness in terms of polynomial time, logspace and first-order reductions makes exactly the same class of problems NP-complete. But there are no problems known to be NP-complete under one of these kinds of reductions but not under one of the others. (Stand by for this paragraph to be edited after people comment!)


1 E.g., Immerman, Descriptive Complexity (Springer, 1999) or Libkin Elements of Finite Model Theory (Springer, 2004).

$\endgroup$
2
  • 2
    $\begingroup$ It's outside of the possibilities you list, but anyway, this problem is known to be NP-complete under zero-error polynomial-time reductions but not known to be NP-hard under deterministic polynomial-time reductions, and by this answer the known hardness can be made effective. ​ ​ $\endgroup$
    – user12859
    Mar 5 '16 at 1:27
  • $\begingroup$ I just learned from here about the "Stop Gap Theorem" - AC$^{\hspace{.02 in}0}$ reductions do not make $\hspace{.91 in}$ "exactly the same class of problems NP-complete." ​ ​ $\endgroup$
    – user12859
    Apr 1 '16 at 6:31
1
$\begingroup$

To answer your first question. Your variable i only ranges in between 1 and T, which is the total number of steps the TM being snapshot takes before halting. Since the TM runs in polynomial time, i.e. $n^c$ for some constant $c$. This the number of bits needed to represent $i$ should only range from 1 to $c \cdot logn$ which is only logarithmic space.

I should also add, that if you think about it, all that you need to compute the next snapshot is, the previous snapshot, $z_{i-1}$ which doesn't vary based on input size. Also the current input tape content which needs at most logn bits as an index, and having to remember when the head had last visited its current working tape position or index it's currently on to re-check its tape contents to determine the next move, which is at most a constant. Thus it can be done under logarithmic space.

The proof for this is laid out in detail in Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach

$\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.