PHOTOCOMPUTING: EXPLORATIONS WITH TRANSPARENCY AND OPACITY
Abstract
We continue to search for methods of parallel computing using light. An algorithm for solving instances of the Boolean satisfiability problem is given and illustrated using a photocopying machine with plastic transparencies as medium. The algorithm solves satisfiability problems in linear time but requires the assumption that information can be stored with a density that is exponential in the number of variables in the problem instance. Consideration is given to situations in which this density limitation is not quite absolute.
References
- , Unconventional Models of Computation UMC'SK, eds.
I. Antoniou , C. S. Calude and M. J. Dineen (Springer, London, 2001) pp. 68–84. Crossref, Google Scholar - , Nanotechnology: Science and Computation, eds.
J. Chen , N. Jonoska and G. Rozenberg (Springer, 2006) pp. 321–331. Crossref, Google Scholar - , Current Developments in Mathematical Biology ,
Series in Knots and Everything 38 , eds.K. Mahdavi , R. Culshaw and J. Boucher ( World Scientific , Singapore , 2007 ) . Google Scholar T. Head , Aqueous solutions of algorithmic problems: emphasizing knights on a 3 × 3, DNA Computing - 7th International Workshop2340,LNCS , eds.N. Jonoska and N. C. Seeman (Springer, 2001) pp. 191–202. Google Scholar- J. Computer Sci. & Tech. 17, 672 (2002). Crossref, ISI, Google Scholar
-
A. M. Pagano and S. Gal , An approach for using modified nucleotides in aqueous DNA computing , Proceedings of the 13th International DNA Computing Workshop ( 2007 ) . Google Scholar - Natural Computing 5, 67 (2005). Crossref, Google Scholar
- Natural Computing . Google Scholar
- Natural Computing . Google Scholar
S. A. Cook , The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing (Assoc. for Computing Machinery, New York, 1971) pp. 151–158. Google Scholar-
M. R. Garey and D. S. Johnson , Computers and Intractability - A Guide to the Theory of NP-Completeness ( W.H. Freeman & Co. , San Francisco , 1979 ) . Google Scholar - Bulletin EATCS 55, 136 (1995). Google Scholar


