Conference Publication Details
Mandatory Fields
Woods, Damien; Gibson J Paul
4th International Conference on Unconventional Computation
Lower bounds on the computational power of an optical model of computation
2005
October
Published
1
()
Optional Fields
237
250
Seville, Spain
We present lower bounds on the computational power of an optical model of computation called the C2-CSM. We show that C2-CSM time is at least as powerful as sequential space, thus giving one of the two inclusions that are necessary to show that the model verifies the parallel computation thesis. Furthermore we show that C2-CSMs that simultaneously use polynomial space and polylogarithmic time decide at least the class NC. © Springer-Verlag Berlin Heidelberg 2005.
Grant Details