Damien Woods' PhD thesis
"Computational Complexity of an optical model of computation" PhD Thesis, NUI Maynooth, 2005. [.pdf] [.ps]
Submitted November 2004
Examined August 2005
Abstract
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 complex-valued 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 application of the complexity theory toolbox to optical computers.
Finally we show that another variation on the model is very powerful; illustrating the power of permitting nonuniformity through arbitrary real inputs.