부산대학교 도서관

Summary: ``A modular query consists of asking how many (modulo $m)$ of$k$ strings belong to a fixed NP language. Modular queries provide aform of restricted access to an NP oracle. For each $k$ and $m$, weconsider the class of languages accepted by NP machines that ask asingle modular query. Han and Thierauf showed that these classescoincide with levels of the Boolean hierarchy when $m$ is even or$k\le2m$, and they determined the exact levels. Until now, theremaining case---odd $m$ and large $k$---looked quite difficult. Wepinpoint the level in the Boolean hierarchy for the remaining case;thus, these classes coincide with levels of the Boolean hierarchy forevery $k$ and $m$.\par ``In addition we characterize the classes obtained by using an ${\rmNP}(l)$ acceptor in place of an NP acceptor $({\rm NP}(l)$ is the$l{\rm th}$ level of the Boolean hierarchy). As before, these allcoincide with levels in the Boolean hierarchy.''