CRCW PRAMの時間計算量の稠密な階層 - 九大コレクション | 九州大学附属図書館

＜紀要論文＞
CRCW PRAMの時間計算量の稠密な階層

作成者	作成者名モルシェド, モンズール Morshed, Manzur 所属機関所属機関名九州大学大学院システム情報工学研究科情報工学専攻 : 博士後期課程 Department of Computer Science and Communication Engineering : Doctoral Program
	作成者名岩本, 宙造 Iwamoto, Chozo イワモト, チュウゾウ所属機関所属機関名九州芸術工科大学 Kyushu Institute of Design
	作成者名岩間, 一雄 Iwama, Kazuo イワマ, カズオ所属機関所属機関名京都大学 Kyoto University
本文言語	日本語
出版者	九州大学大学院システム情報科学研究科
出版者	Graduate School of Information Science and Electrical Engineering, Kyushu University
発行日	1997-09-26
収録物名	九州大学大学院システム情報科学紀要
巻	2
号	2
開始ページ	265
終了ページ	269
出版タイプ	Version of Record
アクセス権	open access
JaLC DOI	https://doi.org/10.15017/1523863
関連DOI	https://portal.isee.kyushu-u.ac.jp/
関連URI	https://portal.isee.kyushu-u.ac.jp/
関連情報	https://portal.isee.kyushu-u.ac.jp/
概要	A hierarchy theorem for parallel time-complexities between constant and 1og n log<log n> is presented. Suppose that t(n) is a function such that there is a TM making (t(n)) ^<Θ (1)> moves and that the ...inverse function t^<- 1>(n) is bounded by O (1og n log<log n>). Then, there exists a language L such that Θ(t^<-1>(n)) time is necessary and sufficient for CRCW PRAMs with polynomially many processors to recognize L.続きを見る

本文ファイル

ファイル	ファイルタイプ	利用条件	サイズ	閲覧回数	説明
p265	pdf	なし	447 KB	299

詳細

PISSN	1342-3819
EISSN	2188-0891
NCID	AN10569524
レコードID	1523863
査読有無	査読有
主題	Computational complexity
	CRCW PRAM
	Parallel computation
登録日	2015.08.24
更新日	2020.10.26