We show that the counting class LWPP remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., $$\rm PP^{Legitimate Deck} = PP$$ ) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning & Torán that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection and acceptance gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the $$\#{\rm P}$$ -based analogue of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. Despite that nonrobustness result for a $$\#{\rm P}$$ -based class, we show that the $$\#{\rm P}$$ -based “exact counting” class $${\rm C}_{=}{\rm P}$$ remains unchanged even if one allows a polynomial number of target values for the number of accepting paths of the machine.

We develop techniques to investigate relativized hierarchical unambiguous computation. We apply our techniques to generalize known constructs involving relativized unambiguity based complexity classes (UP and Promise-UP) to new constructs involving arbitrary higher levels of the relativized unambiguous polynomial hierarchy (UPH). Our techniques are developed on constraints imposed by hierarchical arrangement of unambiguous nondeterministic polynomial-time Turing machines, and so they differ substantially, in applicability and in nature, from standard methods (such as the switching lemma [J. Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, Cambridge, 1987]), which play roles in carrying out similar generalizations. Aside from achieving these generalizations, we resolve a question posed by Cai, Hemachandra, and Vyskoč in [Complexity Theory, Cambridge University Press, Cambridge, UK, 1993, pp. 101–146], on an issue related to nonadaptive Turing access to UP and adaptive smart Turing access to Promise-UP.