Title :
On tally relativizations of BP-complexity classes
Author :
TANG, Shouwen ; Watanabe, Osamu
Author_Institution :
Dept. of Math., California Univ., Santa Barbara, CA, USA
Abstract :
The concept of a random tally set is introduced. Relativization of BP-complexity classes with respect to a tally oracle is considered. Certain results are established and used to show that the BP-polynomial-time hierarchy has properties faithfully reflecting those of the polynomial-time hierarchy; that is, the properties established by relativization yield results for unrelativized cases
Keywords :
computational complexity; polynomials; BP-complexity classes; BP-polynomial-time hierarchy; random tally set; tally relativizations; Mathematics; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5258
