Title :
Circuit lower bounds collapse relativized complexity classes
Author :
Beigel, Richard ; Maciel, Anderson
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Illinois Univ., Chicago, IL, USA
Abstract :
Since the publication of M. Furst et al. (1984) seminal paper connecting AC0 with the polynomial hierarchy, it has been well known that circuit lower bounds allow you to construct oracles that separate complexity classes. We show that similar circuit lower bounds allow you to construct oracles that collapse complexity classes. For example, based on Hastad´s parity lower bound, we construct an oracle such that P=PH⊂⊕P=EXP
Keywords :
computational complexity; polynomials; Hastad´s parity lower bound; circuit lower bounds; oracles; polynomial hierarchy; relativized complexity classes; Argon; Circuits; Computer science; Joining processes; NASA; Polynomials; Turing machines; World Wide Web;
Conference_Titel :
Computational Complexity, 1999. Proceedings. Fourteenth Annual IEEE Conference on
Conference_Location :
Atlanta, GA
Print_ISBN :
0-7695-0075-7
DOI :
10.1109/CCC.1999.766280
