Pinpointing computation with modular queries in the Boolean hierarchy

Agrawal, Manindra ; Beigel, Richard ; Thierauf, Thomas (1996) Pinpointing computation with modular queries in the Boolean hierarchy Lecture Notes in Computer Science, 1180 . pp. 322-334. ISSN 0302-9743

[img]
Preview
PDF - Author Version
201kB

Official URL: http://www.springerlink.com/content/p2926536227686...

Related URL: http://dx.doi.org/10.1007/3-540-62034-6_60

Abstract

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 [HT95] showed that these classes coincide with levels of the Boolean hierarchy when m is even or k≤2m, 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. In addition we characterize the classes obtained by using an NP(l) acceptor in place of an NP acceptor (NP(l) is the lth level of the Boolean hierarchy). As before, these all coincide with levels in the Boolean hierarchy.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:92032
Deposited On:26 May 2012 13:52
Last Modified:19 May 2016 05:37

Repository Staff Only: item control page