In earlier chapters we have used the technique of reducing one problem to another, often as means of demonstrating undecidability. We did this, for instance, in the proof of theorem 6-1.4 by showing that there is a total computable function k such that x ∈ Wx ⇔ ϕk(x) = 0, i.e. we used the function k to transform or reduce each instance of the general problem ‘x ∈ Wx’ to an instance of the general problem ‘ϕx = 0’. In this chapter we consider two ways of making the idea of reducibility precise, and for each we discuss the associated notion of degree (of difficulty) that arises.
It is more convenient to deal with reducibility between sets rather than between problems, remembering that any problem is represented by a set of numbers. The informal idea of a set A being reducible to a set B can be expressed in various ways: for instance
(a) ‘Given a decision procedure for the problem’ x ∈ B’, we can construct one for ‘x ∈ A’.’
(b) ‘For someone who knows all about B, there is a mechanical procedure (that uses his knowledge of B) for deciding questions about A.’
(c) ‘Questions about A are no harder than questions about B.’
(d) ‘The degree of difficulty of the problem’ x ∈ A’ is no greater than that of the problem ‘x ∈ B’.’
It turns out that there are several non-equivalent ways of making this idea precise. The differences between these consist in the manner and extent to which information about B is allowed to be used to settle questions about A. In §§ 1-3 we shall investigate one of the simplest notions of reducibility, called many-one reducibility, which includes all of our earlier uses of the informal idea. In the final sections we shall discuss a more general notion known as Turing reducibility.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.