The PL Hierarchy Collapses
1998; Society for Industrial and Applied Mathematics; Volume: 27; Issue: 5 Linguagem: Inglês
10.1137/s0097539795295924
ISSN1095-7111
Autores Tópico(s)Quantum Computing Algorithms and Architecture
ResumoPrevious article Next article The PL Hierarchy CollapsesMitsunori OgiharaMitsunori Ogiharahttps://doi.org/10.1137/S0097539795295924PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractIt is shown that the PL hierarchy PLH = PL ,\bigcup\limits\, PLPL ,\bigcup\limits\, PLPLPL ,\bigcup\limits\, \cdots$, defined in terms of the Ruzzo--Simon--Tompa relativization, collapses to PL.[1] Google Scholar[2] T. Baker, , J. Gill and , and R. Solovay, Relativizations of the 𝒫=?𝒩𝒫 question, SIAM J. Comput., 4 (1975), pp. 431–442. sim SMJCAT 0097-5397 SIAM J. Comput. LinkGoogle Scholar[3] David Barrington, Bounded‐width polynomial‐size branching programs recognize exactly those languages in NC1, J. Comput. System Sci., 38 (1989), 150–164, 18th Annual ACM Symposium on Theory of Computing (Berkeley, CA, 1986) 91f:68059 CrossrefISIGoogle Scholar[4] Google Scholar[5] Richard Beigel, Perceptrons, PP, and the polynomial hierarchy, Comput. Complexity, 4 (1994), 339–349, Special issue on circuit complexity (Barbados, 1992) 95m:68054 CrossrefGoogle Scholar[6] Richard Beigel, , Nick Reingold and , Daniel Spielman, PP is closed under intersection, J. Comput. System Sci., 50 (1995), 191–202, 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991) 10.1006/jcss.1995.1017 96g:68032 CrossrefISIGoogle Scholar[7] A. Borodin, , S. Cook and , N. Pippenger, Parallel computation for well‐endowed rings and space‐bounded probabilistic machines, Inform. and Control, 58 (1983), 113–136 86j:68038 CrossrefGoogle Scholar[8] Stephen Fenner, , Lance Fortnow and , Stuart Kurtz, Gap‐definable counting classes, J. Comput. System Sci., 48 (1994), 116–148 95d:68047 CrossrefISIGoogle Scholar[9] Lance Fortnow and , Nick Reingold, PP is closed under truth‐table reductions, Inform. and Comput., 124 (1996), 1–6 10.1006/inco.1996.0001 96m:68060 CrossrefISIGoogle Scholar[10] J. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6 (1977), pp. 675–695. sim SMJCAT 0097-5397 SIAM J. Comput. LinkISIGoogle Scholar[11] Neil Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput., 17 (1988), 935–938 90a:68029 LinkISIGoogle Scholar[12] Hermann Jung, On probabilistic time and space, Lecture Notes in Comput. Sci., Vol. 194, Springer, Berlin, 1985, 310–317 87b:68039 Google Scholar[13] R. Ladner and and N. Lynch, Relativization of questions about logspace computability, Math. Systems Theory, 10 (1976), pp. 19–32. aqz MASTBA 0025-5661 Math. Syst. Theory CrossrefGoogle Scholar[14] D. Newman, Rational approximation to |x|, Michigan Math. J., 11 (1964), 11–14 30:1344 CrossrefGoogle Scholar[15] Ramamohan Paturi and , Michael Saks, Approximating threshold circuits by rational functions, Inform. and Comput., 112 (1994), 257–272 10.1006/inco.1994.1059 95e:94066 CrossrefISIGoogle Scholar[16] Charles Rackoff and , Joel Seiferas, Limitations on separating nondeterministic complexity classes, SIAM J. Comput., 10 (1981), 742–745 84f:68035 LinkISIGoogle Scholar[17] John Reif and , Stephen Tate, On threshold circuits and polynomial computation, SIAM J. Comput., 21 (1992), 896–908 93i:68091 LinkISIGoogle Scholar[18] Walter Ruzzo, , Janos Simon and , Martin Tompa, Space‐bounded hierarchies and probabilistic computations, J. Comput. System Sci., 28 (1984), 216–230 86g:68060 CrossrefISIGoogle Scholar[19] Google Scholar[20] Róbert Szelepcsényi, The method of forced enumeration for nondeterministic automata, Acta Inform., 26 (1988), 279–284 89k:68087 CrossrefISIGoogle ScholarKeywordsprobabilistic complexity classesnondeterministic complexity classeslogspace reducibilityconstant-depth circuitsrelativization Previous article Next article FiguresRelatedReferencesCited ByDetails Counting classes and the fine structure between NC1 and LTheoretical Computer Science, Vol. 417 | 1 Feb 2012 Cross Ref Counting Classes and the Fine Structure between NC 1 and LMathematical Foundations of Computer Science 2010 | 1 Jan 2010 Cross Ref The Complexity of Membership Problems for Circuits over Sets of Natural NumbersSTACS 2003 | 17 February 2003 Cross Ref The Complexity of the InertiaFST TCS 2002: Foundations of Software Technology and Theoretical Computer Science | 16 December 2002 Cross Ref On the Enumerability of the Determinant and the RankFoundations of Information Technology in the Era of Network and Mobile Computing | 1 Jan 2002 Cross Ref A note on closure properties of logspace MOD classesInformation Processing Letters, Vol. 75, No. 3 | 1 Aug 2000 Cross Ref Making Nondeterminism UnambiguousKlaus Reinhardt and Eric AllenderSIAM Journal on Computing, Vol. 29, No. 4 | 27 July 2006AbstractPDF (302 KB)Isolation, Matching, and Counting Uniform and Nonuniform Upper BoundsJournal of Computer and System Sciences, Vol. 59, No. 2 | 1 Oct 1999 Cross Ref The Complexity of the Inertia and Some Closure Properties of GapL20th Annual IEEE Conference on Computational Complexity (CCC'05) Cross Ref Volume 27, Issue 5| 1998SIAM Journal on Computing History Published online:28 July 2006 InformationCopyright © 1998 Society for Industrial and Applied MathematicsKeywordsprobabilistic complexity classesnondeterministic complexity classeslogspace reducibilityconstant-depth circuitsrelativizationMSC codes68Q0568Q1068Q15PDF Download Article & Publication DataArticle DOI:10.1137/S0097539795295924Article page range:pp. 1430-1437ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics
Referência(s)