# P/NP - Proof that SAT-TM is NP-complete uses certificate

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

Then:

• 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$$?

• 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$? Jan 24 at 8:44
• 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 Jan 24 at 17:05
• 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). Jan 24 at 19:56
• 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? Jan 24 at 19:57
• It should be $\langle V_w, 1^{q(|w|)} \rangle$, where $q$ is a polynomial that bounds the runtime of the machine $V_w$. Jan 24 at 20:00