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

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
URI:	Publisher
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

Origin of downloads