Lower Bounds on the Computational Power of an Optical Model of Computation

摘要

We present lower bounds on the computational power of an optical model of computation called the C_2-CSM. We show that C_2-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 C_2-CSMs that simultaneously use polynomial space and polylogarithmic time decide at least the class NC.