<紀要論文>
CRCW PRAMの時間計算量の稠密な階層
作成者 | |
---|---|
本文言語 | |
出版者 | |
発行日 | |
収録物名 | |
巻 | |
号 | |
開始ページ | |
終了ページ | |
出版タイプ | |
アクセス権 | |
JaLC DOI | |
関連DOI | |
関連URI | |
関連情報 | |
概要 | 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.続きを見る |
詳細
PISSN | |
---|---|
EISSN | |
NCID | |
レコードID | |
査読有無 | |
主題 | |
登録日 | 2015.08.24 |
更新日 | 2020.10.26 |