THE BOOLEAN HIERARCHY .2. APPLICATIONS

作     者：CAI, JY GUNDERMANN, T HARTMANIS, J HEMACHANDRA, LA SEWELSON, V WAGNER, K WECHSUNG, G 

作者机构：CORNELL UNIVDEPT COMP SCIITHACANY 14853 FRIEDRICH SCHILLER UNIVMATH SECTDDR-6900 JENAGER DEM REP DARTMOUTH COLLDEPT MATH & COMP SCIHANOVERNH 03755 UNIV AUGSBURGINST MATHD-8900 AUGSBURGFED REP GER 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1989年第18卷第1期

页      面：95-111页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Boolean functions Computing Hierarchical file structure 

摘      要：This paper uses the Boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory. The authors show that sparse sets are not unlike Boolean hierarchy in behavior and that in relativized worlds, counting classes are not complete for the levels of the Boolean hierarchy. They demonstrate that calculations of the sparse oracle of the Boolean hierarchy cannot be greatly improved.