The trick to reducing any NP problem (including NP-complete problems) to SAT is
- Write a subroutine that checks the polynomially-sized certificate,
- Convert that routine to a circuit, and
- Flatten the circuit to CNF using the usual
methods.
For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-bit result. Convert the routine to a circuit, then convert the circuit to CNF. Then add simple declarative CNF clauses that force the 2$n$ output variables of the circuit to match the bits of the integer that you want to factor. The resulting CNF instance will be satisfiable only if a bit pattern for the two $n$-bit numbers exists that when multiplied together produces the 2$n$-bit number you want factored. (If you want trivial solutions excluded then you also need to add two extra CNF clauses that demand the most significant $n$-1 bits of each multiplier are not all zero.)
A problem like SUBSET SUM is a bit more intricate. You need to write $n$ routines, each of which returns a particular one of the $n$ integers of the problem set or zero depending on the setting of a parameter bit. These routines feed input into another routine you wrote that sums all $n$ of its inputs and outputs the result. Convert all this into a circuit whose inputs are the parameter bits and whose outputs are the result of the addition routine. Convert the circuit to CNF. Add declarative CNF clauses that force the output variables of the adder routine to match the bits of $k$, the number a solution must sum to. The resulting CNF instance will be satisfiable only if there exists a bit pattern of the parameter bits selecting a subset of the problem set that sums up to $k$.
To show a reduction from SAT to some other problem, I'll copy an answer I gave on the CS stack which shows how to reduce 3-SAT to SUBSET SUM. (See Richard Karp's seminal paper "Reducibility Among Combinatorial Problems" for many more reductions between NP-complete problems.)
The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable. The reduction below is lifted directly from the lecture notes found at https://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf .
We reduce 3SAT to SUBSET-SUM. Consider a 3CNF formula with variables $x_1, . . . , x_n$ and clauses $c_1, . . . , c_r$. For each variable $x_i$, we will have two numbers $y_i$ and $z_i$ in the list. For each clause $c_j$, we will also have two numbers $s_j$ and $t_j$. We define all of these numbers by specifying their base 10 representations. The construction is best explained by an example and a picture.
If the formula is $(x_1∨x_2∨\overline{x_3})∧(\overline{x_1}∨x_2∨\overline{x_3})$, then the base 10 representations of the numbers will look like this:
\begin{array}{c|ccc|cc}
& x_1 & x_2 & x_3 & c_1 & c_2 \\
\hline
y_1 & 1 & 0 & 0 & 1 & 0 \\
z_1 & 1 & 0 & 0 & 0 & 1 \\
y_2 & 0 & 1 & 0 & 1 & 1 \\
z_2 & 0 & 1 & 0 & 0 & 0 \\
y_3 & 0 & 0 & 1 & 0 & 0 \\
z_3 & 0 & 0 & 1 & 1 & 1 \\
\hline
s_1 & 0 & 0 & 0 & 1 & 0 \\
t_1 & 0 & 0 & 0 & 1 & 0 \\
s_2 & 0 & 0 & 0 & 0 & 1 \\
t_2 & 0 & 0 & 0 & 0 & 1 \\
\hline
k & 1 & 1 & 1 & 3 & 3 \\
\end{array}
The number $y_i$ corresponds to the positive occurrences of $x_i$ in the formula while the number $z_i$ corresponds to its negative occurrences. It should be clear how to generalize this construction to an arbitrary 3CNF formula. And the list of numbers can clearly be constructed in polynomial time. We claim that a subset of these numbers adds to exactly $k$ if and only if the formula is satisfiable. A key point is that the sum of the numbers can be done column by column, independently, because carries will never occur.
The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else. The $t$ value will be the same as the $s$ value for each clause.
The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula. Note that the required sum $k$ has a one in each digit position corresponding to the variables. This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both. Note also that sum $k$ has a three in the digit position corresponding to each clause. The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values. All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.
The lesson you should take from all this is that when reducing one NP-complete problem to another the general procedure is to construct gadgets in the target problem that mimic constraint features of the source problem and then use those gadgets to construct a target problem instance that has a solution only if the source problem instance has a solution.
Best Answer
Their "polynomially reduces" means polynomially Turing-reduces, and
their "polynomially transforms" means polynomially many-one reduces.
In standard terminology, which I'll use for this answer,
reduce/reduces/reduction/reductions by default refer to many-one.
"using $g$" / "Turing reduction" mean the same thing, and are defined via oracle machines.
Many-one reductions are equivalent to the special case in which [[the machine always queries
the oracle exactly once] and [the machine always gives the same output as the oracle]].
To compute $\hspace{.04 in}f\hspace{-0.03 in}$, replace "enter the ask state" with "output the contents of the oracle tape".
Now, for $\;\;\;$ many-one reduction $\: \implies \:$ Turing reduction $\;\;\;$:
You have an oracle for $g$ and can evaluate $\hspace{.03 in}f\hspace{-0.03 in}$, so just output $g(\hspace{.05 in}f(x))$. $\:$ It's that simple.
Their definition of NP-hard is correct;
different notions of reduction yield different definitions of NP-hard.
Their definition of NP-complete is missing an important part:
L is NP-complete $\;\; \iff \;\;$ L is NP-hard and L is in NP $\;\;\;\;\;$ .