Share and Export
Share and Export
Woods, Damien (2005) Upper bounds on the computational power of an optical model of computation. In: Algorithms and Computation. Springer, pp. 777-788. ISBN 3-540-30935-7
Preview
DW_upper bounds.pdf
Download (370kB) | Preview
Abstract
We present upper bounds on the computational power of an
optical model of computation called the C2-CSM. We show that C2-CSM
time is no more powerful than sequential space, thus giving one of the
two inclusions that are necessary to show that the model verifies the
parallel computation thesis. Furthermore we show that C2-CSMs that
simultaneously use polynomial space and polylogarithmic time decide
no more than the class NC.
| Item Type: | Book Section |
|---|---|
| Keywords: | Optical Model; Circuit Simulation; Polynomial Space; Image Word; Binary Word; |
| Academic Unit: | Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: | 15740 |
| Depositing User: | Damien Woods |
| Date Deposited: | 28 Mar 2022 14:58 |
| Publisher: | Springer |
| Refereed: | Yes |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/15740 |
| 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
Downloads
Downloads per month over past year
