1
$\begingroup$

I want to check whether I understand the Cook-Levin theorem fully (using the Travelling Salesman Problem as an example).

Given a weighted graph $G$ and an number $L$, the a Travelling Salesman Problem (TSP) is the problem of finding a tour of length at most $L$.

As TSP is in $\mathcal{NP}$ there exists a non-deterministic polynomial time Turing Machine $M$ that can decides the problem; given a graph $G$ and length $L$:

$$ M(G,L) = \left\{ \begin{array}{ll} 1\text{ if there exists a tour in }G\text{ of length at most }L\\ 0\text{ otherwise} \end{array} \right. $$

By the Cook-Levin theorem, such a decider $M$ can be transformed into a Boolean formula that is true if and only if $M$ accepts on $(G,L)$. Let the transformation from the Cook-Levin theorem proof be $R$.

Question 1: Given two deciders $x$ and $y$, if $R(x) = R(y)$ is same Boolean expression, i.e. $x$ and $y$ are transformed into same Boolean formula, What can we say about $x$ and $y$? Are they equivalent?

Also,

Question 2: Is $R$ invertible? Can a Boolean expression be converted to a decider?

$\endgroup$
1
  • 1
    $\begingroup$ Hi, I edited your question a fair bit, in particular I answered your first question via the edits (assuming they get approved!). Please check that the meaning is retained (although there were some misconceptions about the Cook-Levin Theorem that I tried to clear up). $\endgroup$ Commented Mar 23, 2013 at 8:16

1 Answer 1

2
$\begingroup$

Question 1: If two Turing Machines map to the same formula, then yes, they are equivalent - they produce the same output given the same input.

Question 2: Yes, there is at least one proof of the Cook-Levin theorem that would allow in principle the production of an inverse mapping $R^{-1}$, as the variables of the formula explicitly specify the states of the Turing Machine and the transition function. However we can't take any Boolean formula and produce a Turing Machine, all we can say is that $M = R^{-1}(R(M))$.

Now some extra notes and caveats: the Cook-Levin Theorem is not strictly one theorem, both Cook and Levin produced results that are equivalent to what we now call the Cook-Levin theorem. It happens that Garey and Johnson (in: Computers and Intractability) give a reduction that allows the answers I gave above, but this may not be true for all proofs.

Moreover, the reductions that we use routinely for NP-completeness proofs certainly do not satisfy such properties, in particular many source instances can map to a single target instance thus we cannot construct any inverse function nor can we necessarily say anything particular about the source instances.

$\endgroup$
3
  • $\begingroup$ Thank you. @Luke. If x and y is equivalent NDTM, then x and y will be transformed into the same Boolean formula? $\endgroup$
    – martian03
    Commented Mar 23, 2013 at 11:13
  • 1
    $\begingroup$ @HoCheolSHIN, yes and no, they will be transformed into equivalent formulas, so the if the two TMs accept on the same inputs, then the two formula will be true on the same variable assignments. $\endgroup$ Commented Mar 23, 2013 at 11:36
  • $\begingroup$ Thank you @Luke. I realized the relation of transformation. But still I have something confused. I posted a new question about this. $\endgroup$
    – martian03
    Commented Mar 23, 2013 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .