Woods, Damien (2006) Optical computing and computational complexity. In: Unconventional Computation. Springer, pp. 27-40. ISBN 3-540-38593-2
Preview
DW_optical computing.pdf
Download (283kB) | Preview
Abstract
This work concerns the computational complexity of a model
of computation that is inspired by optical computers. The model is called
the continuous space machine and operates in discrete timesteps over a
number of two-dimensional images of fixed size and arbitrary spatial resolution. The (constant time) operations on images include Fourier transformation, multiplication, addition, thresholding, copying and scaling.
We survey some of the work to date on the continuous space machine.
This includes a characterisation of the power of an important discrete
restriction of the model. Parallel time corresponds, within a polynomial,
to sequential space on Turing machines, thus satisfying the parallel computation thesis. A characterisation of the complexity class NC in terms
of the model is also given. Thus the model has computational power that
is (polynomially) equivalent to that of many well-known parallel models.
Such characterisations give a method to translate parallel algorithms to
optical algorithms and facilitate the application of the complexity theory toolbox to optical computers. In the present work we improve on
these results. Specifically we tighten a lower bound and present some
new resource trade-offs.
Item Type: | Book Section |
---|---|
Keywords: | Optical Computing; Computational Complexity; |
Academic Unit: | Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
Item ID: | 15739 |
Depositing User: | Damien Woods |
Date Deposited: | 28 Mar 2022 14:31 |
Publisher: | Springer |
Refereed: | Yes |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/15739 |
Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
Downloads
Downloads per month over past year