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

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 inc...

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2008-03, Vol.7 (1), p.95-108
Main Authors: Woods, Damien, Gibson, J. Paul
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Complex Systems
Computer Science
Evolutionary Biology
Networking and Internet Architecture
Processor Architectures
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-007-9039-7