 These considerations lead naturally to the notion of a degree of difficulty—another concept which can be made precise with respect to different reducibility notions. The version for many-one reducibility is given by the following definition: