JavaScript is disabled for your browser. Some features of this site may not work without it.
Attention submitters: Web accessibility policy to take effect October 15, 2019
For more information, please see our web accessibility policy and web accessibility help for submitters.
For more information, please see our web accessibility policy and web accessibility help for submitters.
The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
Abstract
We show that if the Boolean hierarchy collapses to its $k^{th}$ level, then the polynomial hierarchy collapses to the $k^{th}$ level of the difference hierarchy of $\Sigma^{P}_{2}$ languages.
Date Issued
1989-05Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1008
Type
technical report