To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my professor used the following proof.

Suppose $L$ in NP and $V$ is a verifier for $L$ running in polynomial time of power k. $$L \leq _P \text{SAT-TM} $$ Polynomial reduction function content:

  • Build a TM $V_w$ that takes a certificate $c$ as input and executes $V$ on $\langle w,c\rangle $.
  • Function output: $\langle V_w,q,1^{|w|}\rangle $


  • If $w\in L$, then $V_w$ accepts $c$.
  • Else $w\notin L \rightarrow$ No certificate makes $V_w$ accept, so $\langle V_w,q,1^{|w|}\rangle \notin \text{SAT-TM}$. □

Say we have $L_1 \leq _P L_2 $, my understanding is that the function receives an input of $L_1$ and transforms it so that the existing solution of $L_2$ outputs the same as a solution for $L_1$ would. We have no information about a potential solution and we're extracting it from $L_2$'s output.

But about the certificate, where does he get it and how can it be known inside the polynomial reduction function? Shouldn't the input only be the word $w$?

  • 1
    $\begingroup$ Can you explicitly write the definition of $\text{SAT-TM}$? Also, what do you mean by $q$ when you write the output of the reduction $\langle V_w, q, 1^{|w|}\rangle$? The reduction should output a word, my guess is that it should be $q(1^{|w|})$ or $q(n)$ for some $n$, if so, what is $n$? $\endgroup$ Jan 24 at 8:44
  • $\begingroup$ Its defined as $\text{SAT-TM} := \{ \langle M, 1^k \rangle \;|\; \exists c \in Σ^* \text{such that M accepts c in} \leq \text{k steps}\}$, where M is the description of a turing machine. q is a polynomial and n is for the number of steps, they are there to prove that the function is in polynomial time. I'll simplify the proof without the time variables, for better readability $\endgroup$
    – destabd7
    Jan 24 at 17:05
  • $\begingroup$ Sorry, the definition of SAT-TM and the reduction's output are still not consistent with each other. We can't really help if we don't understand the reduction (including the language we're reducing to). $\endgroup$ Jan 24 at 19:56
  • $\begingroup$ So, if SAT-TM is the language of all machines $M$ and unary numbers $k$, such that $M$ accepts some word in at most $k$ steps. Then, the reduction's output must be a pair, what is the pair? $\endgroup$ Jan 24 at 19:57
  • $\begingroup$ It should be $\langle V_w, 1^{q(|w|)} \rangle$, where $q$ is a polynomial that bounds the runtime of the machine $V_w$. $\endgroup$ Jan 24 at 20:00

Your Answer

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

Browse other questions tagged or ask your own question.