The two sections in this chapter contain work which is related to the work described in chapters 1–4. In section 5.1 we compare the computational difficulty of the listing problem with the difficulty of other computational problems involving combinatorial structures. In section 5.2 we consider a particular computational counting problem which is related to a listing problem described in chapter 4.

Comparing Listing with other Computational Problems

In this section we compare the listing problem with other computational problems involving combinatorial structures. The problems that we consider are described in [JVV 86]. For completeness, we provide a description of the problems here. Suppose that S is a family of combinatorial structures. We consider five computational problems associated with S. In each case the input is a parameter value p of S:

Problem 1 – The Existence Problem

Determine whether or not S(p) = Ø.

Problem 2 – The Construction Problem

If S(p) is non-empty then output a member of an equivalence class in S(p). Otherwise, halt without output.

Problem 3 – The Listing Problem

If S(p) is non-empty then output one representative from each equivalence class in S(p). Otherwise, halt without output.

Problem 4 – The Random Sampling Problem

If S(p) is non-empty then “randomly” choose an equivalence class in S(p) and output a member of that equivalence class. Otherwise, halt without output.