The Boolean Hierarchy of NP-Partitions

1. J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232–1252, 1988.

   Article  MATH  MathSciNet  Google Scholar 

2. J.-Y. Cai and L. Hemachandra. The Boolean hierarchy: hardware over NP. In Proceedings 1st Structure in Complexity Theory Conference, volume 223 of Lecture Notes in Computer Science, pages 105–124. Springer-Verlag, 1986.

   Google Scholar 

3. G. Grätzer. General Lattice Theory. Akademie-Verlag, Berlin, 1978.

   Google Scholar 

4. L. A. Hemaspaandra, A. Hoene, A. V. Naik, M. Ogihara, A. L. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets. International Journal of Foundations of Computer Science, 6(4):403–416, 1995.

   Article  MATH  Google Scholar 

5. U. Hertrampf. Locally definable acceptance types — the three-valued case. In Proceedings 1st Latin American Symposium on Theoretical Informatics, volume 583 of Lecture Notes in Computer Science, pages 262–271, Berlin, 1992. Springer-Verlag.

   Google Scholar 

6. J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263–1282, 1988. Erratum in same journal 20(2):404, 1991.

   Article  MATH  MathSciNet  Google Scholar 

7. J. Köbler, U. Schöning, and K. W. Wagner. The difference and truth-table hierarchies for NP. RAIRO Theoretical Informatics and Applications, 21(4):419–435, 1987.

   MATH  Google Scholar 

8. K. W. Wagner and G. Wechsung. On the boolean closure of NP. Extended abstract as: G. Wechsung. On the boolean closure of NP. Proceedings 5th International Conference on Fundamentals in Computation Theory, volume 199 of Lecture Notes in Computer Science, pages 485–493, Berlin, 1985.

   Google Scholar 

Download references