The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection

• Authors: R. Chang and J. Kadin.
• Cite as: SIAM Journal on Computing, 25(2):340-354, April 1996.
• Previous incarnations:
  • In Proceedings of the 5th Structure in Complexity Theory Conference, 169-178, July 1990.
  • Technical Report 89-1008, Department of Computer Science, Cornell University, May 1989.
• Most readable version: journal version.
• Status: complete.
• Online:
  • Article in SIAM Journals Online: DOI: 10.1137/S0097539790178069.
  • Final journal submission available as a PDF file (with embedded Type 1 fonts): bhe2.pdf.

Abstract: