Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs.

$x\in A$ if and only if

for $i\in N$

$x(i)=0$ or $x(i)=1$

and running time of $x(i)$ is smaller than $n^k$ ($n$ is digit of $i$)

Now consider a $\mathcal{NP}$ problem for the set $A$.

Problem: "For given $x\in A$, is there any $i\in N$, such that $x(i)=0$?"

For this $\mathcal{NP}$ problem, there is a decider of non-deterministic Turing machine $M$

$$ M(x) = \left\{ \begin{array}{ll} 1\text{ if there exists i∈ N, such that x(i)=0 }\\ 0\text{ otherwise} \end{array} \right. $$

And for this NDTM, there is a verifier of polynomial Deterministic Turing Machine $V$,

$$ V(x,i) = \left\{ \begin{array}{ll} 1\text{ if x(i)=0 }\\ 0\text{ otherwise} \end{array} \right. $$

Question : By the Cook-Levin theorem, I think something can be transformed into a Boolean formula. What is transformed into a Boolean formula?

$M$? $M(x)$? $V$? $V(x)$? $x$? or the NP problem itself?

share|improve this question

1 Answer

up vote 1 down vote accepted

The usual version of the Cook-Levin theorem provides a transformation from the decider $M$, but the truth value of the variables is (partially) set by the input $x$. That is, there are variables of the form $S_{i,\rho}$ which are true if the $i$th symbol on the input tape is $\rho$ (so you have about $n\times|\Sigma|$ of these, where $n$ is the length of encoding of the input and $\Sigma$ is the input alphabet).

It would not be too hard to imagine that there would be an alternate proof that usese $V$ instead of $M$. Indeed, Levin's proof mapped from search problems, rather than decisions problems anyway. The key part in any such proof though is that we need to be able to map any problem in $\mathcal{NP}$ to SAT. Thus we need to use some universal property of all problems in $\mathcal{NP}$, such as that they all have a NDTM that decides them, or a DTM that verifies them.

share|improve this answer
Thanks @Luke. Let A be a set of all NP problem. Let B be a set of all decider of NP problem. Let C be a set of all verifier of NP problem. Let D be a set of all Boolean formula. You mean that there are transformations from A to D, from B to D, from C to D respectively? – HoCheol SHIN Mar 24 at 19:00
1  
@HoCheolSHIN, yes, though the Cook-Levin theorem is typically B -> D. – Luke Mathieson Mar 24 at 23:22
Thank you Luke! – HoCheol SHIN Mar 27 at 2:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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