MURAL - Maynooth University Research Archive Library



    Optical computing and computational complexity


    Woods, Damien (2006) Optical computing and computational complexity. In: Unconventional Computation. Springer, pp. 27-40. ISBN 3-540-38593-2

    [thumbnail of DW_optical computing.pdf]
    Preview
    Text
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads