Unambiguous Computations and Locally De nable Acceptance Types

Hertrampf's locally denable acceptance types show that many complexity classes can be dened in terms of polynomial time bounded NTM's with simple local conditions on the nodes of its computation tree, rather than global concepts like number of accepting paths etc. We introduce a modication of Hertrampf's lo-cally denable acceptance types which allows to get a larger number of charac-terizable complexity classes. Among others the newly characterizable classes are UP and ModZ k P. It is shown how dierent types of oracle access, e.g., guarded access, can be characterized by this model. This sheds new light on the discus-sion on how to access unambiguous computation. We present simple functions that describe precisely objects of current research as the unambiguous oracle, al-ternation, and promise hierarchies. We exhibit the new class UAP which seems to be an unambiguous analogue of Wagner's rP. UAP (and thus rP) contains Few and is currently the smallest class known with this property. Theoretical Computer Science, Vol. 194, pp. 137–161, 1998