Thumbnail
Access Restriction
Subscribed

Author Balczar, Jose L. ♦ Book, Ronald V. ♦ Schning, Uwe
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1986
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with others comparing the union of the hierarchy with certain probabilistic classes. In each case it is shown that the answer is “yes” if and only if for every sparse set $\textit{S},$ the answer is “yes” when the classes are relativized to $\textit{S}$ if and only if there exists a sparse set $\textit{S}$ such that the answer is “yes” when the classes are relativized to $\textit{S}.$ Thus, in each case the question is answered if it is answered for any arbitrary sparse oracle set.Long and Selman first proved that the polynomial-time hierarchy collapses if and only if for every sparse set $\textit{S},$ the hierarchy relative to $\textit{S}$ collapses. This result is re-proved here by a different technique.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1986-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 33
Issue Number 3
Page Count 15
Starting Page 603
Ending Page 617


Open content in new tab

   Open content in new tab
Source: ACM Digital Library