The many-one equivalence of some general combinatorial decision problems

Abstract

A decision problem for a combinatorial system shall denote a pair ($, S) where <f> is a specified kind of decision problem (e.g. derivability problem, halting problem, etc.) and 5 is a combinatorial system. Two decision problems (<i, Si), ($ 2 , 2) are sa ^d t0 be of the same many-one degree (of unsolvability) if there exist effective many-one mappings and g such that each instance of ($1, Si) is reducible to an instance of ($2, S2) via and each instance of (02, S 2 ) is reducible to an instance of (</>i, Si) via g.