Computational complexity of an optical model of computation

We investigate the computational complexity of an optically inspired model of computation. The model is called the continuous space machine and operates in discrete timesteps over a number of two-dimensional complexvalued images of constant size and arbitrary spatial resolution. We define a number of optically inspired complexity measures and data representations for the model. We show the growth of each complexity measure under each of the model’s operations. We characterise the power of an important discrete restriction of the model. Parallel time on this variant of the model is shown to correspond, within a polynomial, to sequential space on Turing machines, thus verifying the parallel computation thesis. We also give a characterisation of the class NC. As a result the model has computational power equivalent to that of many well-known parallel models. These characterisations give a method to translate parallel algorithms to optical algorithms and facilitate the applicatio