Abstract

We present an optical computing system to solve NP-hard problems. As nano-optical computing is a promising venue for the next generation of computers performing parallel computations, we investigate the application of submicron, or even subwavelength, computing device designs. The system utilizes a setup of exponential sized masks with exponential space complexity produced in polynomial time preprocessing. The masks are later used to solve the problem in polynomial time. The size of the masks is reduced to nanoscaled density. Simulations were done to choose a proper design, and actual implementations show the feasibility of such a system.

© 2013 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010).
    [CrossRef]
  2. J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.
  3. J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
    [CrossRef]
  4. S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).
  5. M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Proceedings of Unconventional Computing, C. Calude, M. J. Dinneen, G. Păun, G. Rozenberg, and S. Stepney, eds., Vol. 4135 of Lecture Notes in Computer Science (Springer-Verlag, 2006), pp. 217–227.
  6. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007).
    [CrossRef]
  7. S. Dolev and H. Fitoussi, “Primitive operations for graph-optical processor,” presented at 6th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, May2006.
  8. S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).
  9. S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
    [CrossRef]
  10. E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.
  11. D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007).
    [CrossRef]
  12. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT, 1988).
  13. A. D. McAulay, Optical Computer Architectures (Wiley, 1991).
  14. A. Hyman, Charles Babbage: Pioneer of the Computer (Princeton University, 1982).
  15. S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).
  16. Lenslet LTD, “Lenslet Demonstrates First Commercial Optical Processor,” http://www.taborcommunications.com/hpcwire/hpcwireWWW/03/1017/106185.html .
  17. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
    [CrossRef]
  18. D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.
  19. P. van Emde Boas, “Machine models and simulation,” in Handbook of Theoretical Computer Science, Vol.  A of Algorithms and Complexity (Elsevier, 1990), pp. 1–66.
  20. S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).
  21. A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010).
    [CrossRef]
  22. H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).
  23. W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.
  24. S. Goliaei and M.-H. Foroughmand-Araabi, “Lower bounds on the complexity of the wavelength-based machine,” in Unconventional Computation and Natural Computation, Vol. 7445 of Lecture Notes in Computer Science (2012), pp. 94–105.
  25. B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
    [CrossRef]
  26. W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
    [CrossRef]

2013 (1)

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

2012 (1)

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

2010 (3)

A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010).
[CrossRef]

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010).
[CrossRef]

S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
[CrossRef]

2007 (3)

1994 (1)

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
[CrossRef]

Anter, A.

A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010).
[CrossRef]

Arora, S.

S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).

Barak, B.

S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).

Bermak, A.

W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.

Boussaid, F.

W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.

Caulfield, H. J.

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010).
[CrossRef]

Cohen, E.

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

Dolev, S.

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010).
[CrossRef]

S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
[CrossRef]

A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010).
[CrossRef]

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).

S. Dolev and H. Fitoussi, “Primitive operations for graph-optical processor,” presented at 6th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, May2006.

S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).

D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.

S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).

Feitelson, G.

G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT, 1988).

Fitoussi, H.

S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
[CrossRef]

S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).

S. Dolev and H. Fitoussi, “Primitive operations for graph-optical processor,” presented at 6th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, May2006.

Foroughmand-Araabi, M.-H.

S. Goliaei and M.-H. Foroughmand-Araabi, “Lower bounds on the complexity of the wavelength-based machine,” in Unconventional Computation and Natural Computation, Vol. 7445 of Lecture Notes in Computer Science (2012), pp. 94–105.

Frenkel, S.

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

Goliaei, S.

S. Goliaei and M.-H. Foroughmand-Araabi, “Lower bounds on the complexity of the wavelength-based machine,” in Unconventional Computation and Natural Computation, Vol. 7445 of Lecture Notes in Computer Science (2012), pp. 94–105.

Gutfreund, D.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007).
[CrossRef]

Haist, T.

Hyman, A.

A. Hyman, Charles Babbage: Pioneer of the Computer (Princeton University, 1982).

Idrobo, J. C.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Korach, E.

S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).

Kryzhanovsky, B. V.

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Lee, J.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Mann, H. J.

H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).

McAulay, A. D.

A. D. McAulay, Optical Computer Architectures (Wiley, 1991).

Melikyan, A. O.

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Messika, S.

Nanda, J.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Oltean, M.

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Proceedings of Unconventional Computing, C. Calude, M. J. Dinneen, G. Păun, G. Rozenberg, and S. Stepney, eds., Vol. 4135 of Lecture Notes in Computer Science (Springer-Verlag, 2006), pp. 217–227.

Osten, W.

Palagushkin, A. N.

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Pantelides, S. T.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Pennycook, S. J.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Prokopenko, S. A.

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Puzis, R.

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

Reif, J. H.

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
[CrossRef]

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.

Rosen, J.

Rosenblit, M.

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

Seitz, G.

H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).

Sergeev, A. P.

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Shaked, N. T.

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.

Shaltiel, R.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007).
[CrossRef]

Tamir, D. E.

D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.

Ta-Shma, A.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007).
[CrossRef]

Tygar, D.

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
[CrossRef]

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.

Ulrich, W.

H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).

Uzan, G.

S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).

van Emde Boas, P.

P. van Emde Boas, “Machine models and simulation,” in Handbook of Theoretical Computer Science, Vol.  A of Algorithms and Complexity (Elsevier, 1990), pp. 1–66.

Wilson, P. J.

D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.

Xiajun, W.

W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.

Yoshida, A.

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
[CrossRef]

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.

Yuval, N.

S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).

Zhao, X.

W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.

Zhou, W.

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Appl. Opt. (1)

Comput. Complex. (1)

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007).
[CrossRef]

Discrete Comput. Geom. (1)

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994).
[CrossRef]

Nat. Nanotechnol. (1)

W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012).
[CrossRef]

Nat. Photonics (1)

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010).
[CrossRef]

Natural Comput. (1)

A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010).
[CrossRef]

Opt. Express (1)

Opt. Mem. Neural Netw. (1)

B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013).
[CrossRef]

Theor. Comput. Sci. (1)

S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
[CrossRef]

Other (17)

E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.

S. Dolev and H. Fitoussi, “Primitive operations for graph-optical processor,” presented at 6th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, May2006.

S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).

J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.

S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Proceedings of Unconventional Computing, C. Calude, M. J. Dinneen, G. Păun, G. Rozenberg, and S. Stepney, eds., Vol. 4135 of Lecture Notes in Computer Science (Springer-Verlag, 2006), pp. 217–227.

G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT, 1988).

A. D. McAulay, Optical Computer Architectures (Wiley, 1991).

A. Hyman, Charles Babbage: Pioneer of the Computer (Princeton University, 1982).

S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).

Lenslet LTD, “Lenslet Demonstrates First Commercial Optical Processor,” http://www.taborcommunications.com/hpcwire/hpcwireWWW/03/1017/106185.html .

D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.

P. van Emde Boas, “Machine models and simulation,” in Handbook of Theoretical Computer Science, Vol.  A of Algorithms and Complexity (Elsevier, 1990), pp. 1–66.

S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).

H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).

W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.

S. Goliaei and M.-H. Foroughmand-Araabi, “Lower bounds on the complexity of the wavelength-based machine,” in Unconventional Computation and Natural Computation, Vol. 7445 of Lecture Notes in Computer Science (2012), pp. 94–105.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1.
Fig. 1.

Example of a three-node Hamiltonian cycle optical mask setup.

Fig. 2.
Fig. 2.

Example of the masks for a Hamiltonian cycle with (a) a 3D structure of n = 4 and (b) 2D front view of n = 5 .

Fig. 3.
Fig. 3.

Distribution of the light passing through the mask holes.

Fig. 4.
Fig. 4.

Images of different masks using an electron microscope, obtained by reflected electrons (RE), secondary electrons (SE), and the topographic contrast (TE).

Fig. 5.
Fig. 5.

The design of the array of masks (left), and an enlargement of one mask (right).

Fig. 6.
Fig. 6.

Output of different mask setups. Mask numberings are according to the notations on Fig. 2. Setups include (a) three layers that allow one pixel, (b) four layers that allow one pixel, and (c) three layers that block all the light.

Fig. 7.
Fig. 7.

Test (top) and simulation (bottom) of a setup using masks 31, 43, 23, and 52 of Fig. 2.

Fig. 8.
Fig. 8.

Test (top) and simulation (bottom) of a setup using masks 25, 35, 24, and 52 of Fig. 2.

Fig. 9.
Fig. 9.

Test (top) and simulation (bottom) of a setup using masks 35, 34, 24, and 52 of Fig. 2.

Fig. 10.
Fig. 10.

Test (top) and simulation (bottom) of a setup using masks 35, 52, 45, and 54 of Fig. 2.

Tables (1)

Tables Icon

Table 1. Assigned Edges of Three-Node Graph

Equations (2)

Equations on this page are rendered with MathJax. Learn more.

M 3 = ( 1 0 0 1 1 0 0 1 1 0 0 1 ) M 4 = ( 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 ) .
V 3 = ( e 12 e 13 e 21 e 23 e 31 e 32 ) , V 4 = ( e 12 e 13 e 14 e 21 e 23 e 24 e 31 e 32 e 34 e 41 e 42 e 43 ) .

Metrics