• DocumentCode
    2112187
  • Title

    Parallel complexity hierarchies based on PRAMs and DLOGTLME-uniform circuits

  • Author

    Iwama, Kazuo ; Iwamoto, Chuzo

  • Author_Institution
    Dept. of Comput. Sci. & Commun. Eng., Kyushu Univ., Fukuoka, Japan
  • fYear
    1996
  • fDate
    24-27 May 1996
  • Firstpage
    24
  • Lastpage
    32
  • Abstract
    Unlike the case of logspace-uniform circuits, complexity hierarchies do exist for PRAMs and DLOGTIME-uniform circuits: (i) There exist a constant d and a language L such that L is recognizable in time dT(n) by some PRIORITY CRCW PRAM but is not recognizable in time T(n) by any PRIORITY CRCW PRAM if the number of processors is fixed. (ii) There exist constants c, d and a language L such that L is recognizable by some family of DLOGTIME-uniform circuits of size (Z(n))c and depth dT(n) but is not recognizable by any family of DLOGTIME-uniform circuits of size Z(n) and depth T(n) if T(n) is not bounded by O(log n)
  • Keywords
    computational complexity; parallel algorithms; DLOGTIME-uniform circuits; PRAMs; PRIORITY CRCW PRAM; complexity hierarchies; parallel complexity; Circuits; Computer science; Phase change random access memory; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
  • Conference_Location
    Philadelphia, PA
  • Print_ISBN
    0-8186-7386-9
  • Type

    conf

  • DOI
    10.1109/CCC.1996.507665
  • Filename
    507665