부산대학교 도서관

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