# About Cook–Levin theorem

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?

• 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). Commented Mar 23, 2013 at 8:16

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