Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
Jim Kadin · SIAM Journal on Computing · 1991
Previous article Full AccessErratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy CollapsesJim KadinJim Kadinhttps://doi.org/10.1137/0220025PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses." SIAM Journal on Computing, 20(2), p. 404[1] Jim Kadin, The polynomial time hierarchy collapses if the Boolean hierarchy collapses, SIAM J. Comput., 17 (1988), 1263–1282 10.1137/0217080 90a:03060 0664.03031 LinkISIGoogle Scholar[2] Richard Chang and , Jim Kadin, The Boolean hierarchy and the polynomial hierarchy: a closer connectionFifth Annual Structure in Complexity Theory Conference (Barcelona, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 169–178, July 1 097 667 CrossrefGoogle Scholar[3] S. Mahaney, 1989, Private communication Google Scholar[4] K. Wagner, Number-of-query hierarchies, Tech. Report, 158, University of Augsburg, Augsburg, Federal Republic of Germany, 1987, October Google Scholar[5] K. Wagner, Number-of-query hierarchies, Tech. Report, 4, Institut für Informatik, Universität Würzburg, Würzburg, Federal Republic of Germany, 1989, February Google Scholar[6] C. Yap, Some consequences of nonuniform conditions on uniform classes, Theoret. Comput. Sci., 26 (1983), 287–300 10.1016/0304-3975(83)90020-8 85i:03133 0541.68017 CrossrefISIGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Structure in Approximation ClassesPierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, and linebreak Luca Trevisan28 July 2006 | SIAM Journal on Computing, Vol. 28, No. 5AbstractPDF (460 KB)Recognizing when greed can approximate maximum independent sets is complete for parallel access to NPInformation Processing Letters, Vol. 65, No. 3 Cross Ref The Boolean Hierarchy and the Polynomial Hierarchy: A Closer ConnectionRichard Chang and Jim Kadin13 July 2006 | SIAM Journal on Computing, Vol. 25, No. 2AbstractPDF (1691 KB)Bounded queries to arbitrary sets8 January 2011 | RAIRO - Theoretical Informatics and Applications, Vol. 30, No. 2 Cross Ref Volume 20, Issue 2| 1991SIAM Journal on Computing History Submitted:18 October 1990Accepted:14 November 1990Published online:31 July 2006 InformationCopyright © 1991 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0220025Article page range:pp. 404-404ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics