| Creator |
|
|
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| JaLC DOI |
|
| Related DOI |
|
| Related URI |
|
| Relation |
|
| Abstract |
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.show more
|
Export Mendeley
p265