[proofplan] The witness-conversion and witness-decoding hypotheses, understood relative to the fixed verifiers $V_A$ and $V_B$, prove that the construction preserves yes-instances in both directions for every encoded string: $x \in A$ if and only if $f(x) \in B$. Since $f$ is computable in polynomial time, this gives a polynomial-time many-one reduction $A \le_p B$; the witness transformations need only exist, since they are used to prove language equivalence rather than to compute the reduction. Because $A$ is NP-complete, every language in $\mathrm{NP}$ reduces to $A$, and composing reductions gives a polynomial-time reduction to $B$. Thus $B$ is NP-hard, and the separate hypothesis $B \in \mathrm{NP}$ upgrades NP-hardness to NP-completeness. [/proofplan] [step:Use the witness maps to prove equivalence of yes-instances] Let $\Sigma$ be the fixed finite alphabet used to encode instances. Let $V_A: \Sigma^* \times \Sigma^* \to \{0,1\}$ and $V_B: \Sigma^* \times \Sigma^* \to \{0,1\}$ be the verifiers for $A$ and $B$ appearing in the completeness and soundness hypotheses. The theorem statement asserts witness conversion and decoding existentially; for notation, whenever $V_A(x,w)=1$, write $C(x,w) \in \Sigma^*$ for one converted certificate whose existence is supplied by completeness, and whenever $V_B(f(x),z)=1$, write $D(x,z) \in \Sigma^*$ for one decoded certificate whose existence is supplied by soundness. These certificate choices are used only to prove equivalence of yes-instances; no polynomial-time bound on them is needed for the many-one reduction. Let $x \in \Sigma^*$ be an arbitrary encoded string. We prove $x \in A \iff f(x) \in B$. Assume first that $x \in A$. Since $V_A$ is a verifier for $A$, there exists a certificate $w \in \Sigma^*$ such that $V_A(x,w)=1$. By the completeness hypothesis for the gadget construction, the certificate $C(x,w) \in \Sigma^*$ satisfies $V_B(f(x),C(x,w))=1$. Since $V_B$ verifies $B$, this implies $f(x) \in B$. Conversely, assume that $f(x) \in B$. Since $V_B$ is a verifier for $B$, there exists a certificate $z \in \Sigma^*$ such that $V_B(f(x),z)=1$. By the soundness hypothesis for the gadget construction, the decoded certificate $D(x,z) \in \Sigma^*$ satisfies $V_A(x,D(x,z))=1$. Since $V_A$ verifies $A$, this implies $x \in A$. [guided] The goal of a many-one reduction is not merely to build an instance $f(x)$ of $B$; it must preserve the yes/no answer. The witness maps give exactly that preservation. Let $x \in \Sigma^*$ be an arbitrary encoded string. The certificate transformations are understood existentially relative to the fixed verifiers $V_A$ and $V_B$: when an accepting $A$-certificate $w$ is present, completeness supplies a converted certificate denoted $C(x,w)$, and when an accepting $B$-certificate $z$ is present, soundness supplies a decoded certificate denoted $D(x,z)$. These choices are not the reduction itself. The reduction is the map $f$, so only $f$ must be computable in polynomial time; the certificate transformations are used here to prove that $f$ preserves membership. We first prove the forward implication. Suppose $x \in A$. Because $V_A$ is a verifier for $A$, membership of $x$ in $A$ means that there exists a certificate $w \in \Sigma^*$ with $V_A(x,w)=1$. The completeness direction of the gadget construction says that any accepting witness for the original instance can be transformed into an accepting witness for the constructed instance. Applying that hypothesis to $x$ and $w$, the string $C(x,w)$ satisfies $V_B(f(x),C(x,w))=1$. Since $V_B$ is a verifier for $B$, this proves $f(x) \in B$. Now prove the reverse implication. Suppose $f(x) \in B$. Since $V_B$ verifies $B$, there exists a certificate $z \in \Sigma^*$ such that $V_B(f(x),z)=1$. The soundness direction says that every accepting witness for the constructed $B$-instance can be decoded into an accepting witness for the original $A$-instance. Applying that hypothesis to $x$ and $z$, the string $D(x,z)$ satisfies $V_A(x,D(x,z))=1$. Since $V_A$ verifies $A$, this proves $x \in A$. Thus the construction preserves membership in both directions: $x \in A \iff f(x) \in B$. [/guided] [/step] [step:Recognize the construction as a polynomial-time many-one reduction] The map $f: \Sigma^* \to \Sigma^*$ is polynomial-time computable by hypothesis. The previous step proved that, for every encoded instance $x$ of $A$, $x \in A \iff f(x) \in B$. Therefore $f$ is a polynomial-time many-one reduction from $A$ to $B$, so $A \le_p B$. [guided] A polynomial-time many-one reduction from $A$ to $B$ is a polynomial-time computable map $f: \Sigma^* \to \Sigma^*$ such that every input string has the same yes/no status after applying $f$: $x \in A \iff f(x) \in B$. We verify these two requirements separately. First, the map $f: \Sigma^* \to \Sigma^*$ is polynomial-time computable by the construction hypothesis. Second, the previous step proved the membership equivalence $x \in A \iff f(x) \in B$ for every encoded string $x \in \Sigma^*$. Hence $f$ satisfies exactly the definition of a polynomial-time many-one reduction from $A$ to $B$, and we may write $A \le_p B$. [/guided] [/step] [step:Transfer NP-hardness from $A$ to $B$] Let $L$ be any language in $\mathrm{NP}$. If $L$ is originally encoded over another finite alphabet $\Gamma$, fix any injective block code $\Gamma \to \Sigma^m$ for some $m \in \mathbb{N}$ and extend it symbol-by-symbol to strings; this recoding and its inverse on valid codewords are computable in linear time, so polynomial-time many-one reducibility is unchanged. We therefore regard $L$ over the fixed alphabet $\Sigma$. Since $A$ is NP-complete, $A$ is NP-hard, so there exists a polynomial-time computable map $g: \Sigma^* \to \Sigma^*$ such that, for every string $y \in \Sigma^*$, $y \in L \iff g(y) \in A$. Define the composite map $h: \Sigma^* \to \Sigma^*$ by the rule $h(y)=f(g(y))$ for every $y \in \Sigma^*$. Because $g$ and $f$ are polynomial-time computable, their composition $h=f \circ g$ is polynomial-time computable. For every $y \in \Sigma^*$, using first the reduction from $L$ to $A$ and then the reduction from $A$ to $B$, we obtain $y \in L \iff g(y) \in A$. The string $g(y)$ belongs to $\Sigma^*$ because $g: \Sigma^* \to \Sigma^*$. Since the previous step proved the equivalence $u \in A \iff f(u) \in B$ for every string $u \in \Sigma^*$, we may apply it with $u=g(y)$ and get $g(y) \in A \iff f(g(y)) \in B$. Hence $y \in L \iff h(y) \in B$. Thus every language $L \in \mathrm{NP}$ admits a polynomial-time many-one reduction to $B$, so $B$ is NP-hard. [guided] To prove that $B$ is NP-hard, we must show that every language $L \in \mathrm{NP}$ has a polynomial-time many-one reduction to $B$. Let $L$ be an arbitrary language in $\mathrm{NP}$. If $L$ is encoded over a different finite alphabet $\Gamma$, choose an injective block code $\Gamma \to \Sigma^m$ for some $m \in \mathbb{N}$ and extend it to strings by concatenating codewords. Encoding and decoding valid codewords take time linear in the string length, so replacing $\Gamma$ by $\Sigma$ changes reduction maps only by linear-time pre- and post-processing. Thus it is harmless to regard $L$ over the fixed alphabet $\Sigma$. Since $A$ is NP-complete, it is NP-hard. Therefore there is a polynomial-time computable map $g: \Sigma^* \to \Sigma^*$ such that, for every string $y \in \Sigma^*$, we have $y \in L \iff g(y) \in A$. From the previous step, the construction map $f: \Sigma^* \to \Sigma^*$ is a polynomial-time many-one reduction from $A$ to $B$, so for every string $u \in \Sigma^*$ we have $u \in A \iff f(u) \in B$. Define $h: \Sigma^* \to \Sigma^*$ by $h(y)=f(g(y))$ for every $y \in \Sigma^*$. The map $h$ is polynomial-time computable because it is the composition of the polynomial-time computable maps $g$ and $f$. Now fix $y \in \Sigma^*$. The first reduction gives $y \in L \iff g(y) \in A$. Since $g(y) \in \Sigma^*$, we may apply the second reduction to the string $u=g(y)$ and obtain $g(y) \in A \iff f(g(y)) \in B$. Combining these two equivalences gives $y \in L \iff h(y) \in B$. Thus $h$ is a polynomial-time many-one reduction from the arbitrary language $L \in \mathrm{NP}$ to $B$. Since $L$ was arbitrary, every language in $\mathrm{NP}$ reduces to $B$, and therefore $B$ is NP-hard. [/guided] [/step] [step:Combine NP-hardness with membership in NP] By hypothesis, $B \in \mathrm{NP}$. The previous step proved that $B$ is NP-hard. Therefore $B$ is both in $\mathrm{NP}$ and NP-hard, which is precisely the definition of NP-completeness. Hence $B$ is NP-complete. [guided] The final step uses the definition of NP-completeness. A decision problem is NP-complete exactly when it satisfies two conditions: it belongs to $\mathrm{NP}$, and it is NP-hard. The first condition is one of the hypotheses: $B \in \mathrm{NP}$. The second condition was proved in the previous step: every language in $\mathrm{NP}$ admits a polynomial-time many-one reduction to $B$, so $B$ is NP-hard. Combining these two facts, $B$ is NP-complete. This proves the theorem. [/guided] [/step]