The one-one equivalence of some general combinatorial decision problems.
Charles E. Hughes, Wilson E. Singletary · Notre Dame Journal of Formal Logic · 1977
Introduction A general combinatorial decision problem may be defined quite simply to be a family of related decision problems concerned with some class of combinatorial systems.E.g., the general halting problem for Turing machines is the family of halting problems ranging over all Turing machines.Let G λ and G 2 be two general combinatorial decision problems.G γ is said to be one-one {many-one) reducible to G 2 if there exists an effective mapping ψ from the problems p in d into the problems ψ(p) in G 2 such that p is of the same one-one (many-one) degree as ψ(p).(Actually if p is solvable we only require that ψ(p) be also solvable.)G± and G 2 are said to be one-one {many-one) equivalent if each is one-one (many-one) reducible to the other.Recent research by the authors and Overbeek [2, 3, 4, 5, 6, 7, and 10] has demonstrated the many-one equivalence of a large number of general combinatorial decision problems.In this paper* we will show that some of these general decision problems are in fact one-one equivalent.Our method of proof, which has been used by Cleave [l] to study "system functions", is to show that each non-recursive instance of the general decision problems under consideration is a cylinder.Since many-one equivalence of cylinders implies one-one equivalence, the desired results are achieved.2 Cylinders and their properties Let R be an arbitrary recursively enumerable (r.e.) set.R is called a cylinder if the decision problem for membership in R is of the same one-one degree as that for the set of pairs {(x, n)\xe R and n is a natural number}.That is to say, R is a cylinder if it may be placed in an effective one-one correspondence with the cartesian