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
Link To Document