One of the problems in complexity theory is that the same types of results seem to be proven over and over for different classes, even though the spirit of the proof is similar for the different classes. It would be natural to seek a notion of class sufficiently abstract that it would allow one to unify such proofs into a single metaproof.

The authors of this paper approached this insightfully in their earlier paper [1], and this paper continues that approach. In brief, their approach works by defining classes in terms of the pair of languages describing the acceptance and rejection patterns of nondeterministic machines accepting languages of the class, where each computation path outputs a 0 for rejection and a 1 for acceptance. So, for example, NP is the class associated with the acceptance pattern language (0+1)*1(0+1)* and the rejection pattern language 0*. Of course, for promise-like classes such as UP, there may be patterns that fall in neither the rejection pattern language nor the acceptance pattern language. This paper’s main result is to derive a sufficient condition, in terms of the just-mentioned approach, for the statement D ⊆ C ↔ ( ∀ S ∈ SPARSE ) [ D ^S ⊆ C ^S ]. The condition involves, in part, whether D robustly possesses complete sets--an issue their earlier paper completely characterizes in terms of their acceptance/rejection pattern approach. This paper also derives a sufficient condition for when class inclusion robust with respect to tally oracles holds if and only if class inclusion with respect to sparse oracles holds.