MURAL - Maynooth University Research Archive Library



    Lower bounds on the computational power of an optical model of computation


    Woods, Damien and Gibson, J. Paul (2008) Lower bounds on the computational power of an optical model of computation. Natural Computing, 7 (1). pp. 95-108. ISSN 1567-7818

    [thumbnail of Woods_Lower_2008.pdf]
    Preview
    Text
    Woods_Lower_2008.pdf

    Download (947kB) | Preview

    Abstract

    This work is concerned with the computational complexity of a model of computation that is inspired by optical computers. We present lower bounds on the computational power of the model. Parallel time on the model is shown to be at least as powerful as sequential space. This gives one of the two inclusions that are needed to show that the model verifies the parallel computation thesis. As a corollary we find that when the model is restricted to simultaneously use polylogarithmic time and polynomial space, its power is lower bounded by the class NC. By combining these results with the known upper bounds on the model, we find that the model verifies the parallel computation thesis and, when suitably restricted, characterises NC.
    Item Type: Article
    Keywords: Turing Machine; Optical Computer; Polynomial Space; Optical Computing; Nondeterministic Turing Machine;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 12418
    Identification Number: 10.1007/s11047-007-9039-7
    Depositing User: Damien Woods
    Date Deposited: 17 Feb 2020 14:37
    Journal or Publication Title: Natural Computing
    Publisher: Elsevier
    Refereed: Yes
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/12418
    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