The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses

Thumbnail
View/Open
PERMANENT LINK(S)
https://hdl.handle.net/1813/6683
Collections
Metadata
Show full item record
Author
Kadin, Jim
Abstract
The structure of the Boolean hierarchy (BH) is related to the polynomial time hierarchy (PH) by showing that if the BH collapses, then $PH \subseteq \Delta^{P}_{3}$.
Date Issued
1987-06
Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-843
Type
technical report

Statistics