 The notion of reducibility has its origins in the work of Turing and Post who considered several variants of computability (Post 1947; Turing 1939). The concept was later appropriated in the context of computational complexity theory and is today one of the basic concepts of both computability and computational complexity theory (Odifreddi 1989; Sipser 1996). Roughly speaking, a reduction of a problem \(D_i\) to a problem \(D_j\) comes down to providing an effective procedure for translating every instance \(d_{i,m}\) of the problem \(D_i\) to an instance \(d_{j,n}\) of \(D_j\) in such a way that an effective procedure for solving \(d_{j,n}\) also yields an effective procedure for solving \(d_{i,m}\). In other words, if \(D_i\) reduces to \(D_j\) then, if \(D_i\) is uncomputable so is \(D_j\). Note that the reduction of one problem to another can also be used in decidability proofs: if \(D_i\) reduces to \(D_j\) and \(D_j\) is known to be computable then so is \(D_i\).