Optical solutions to NP-Complete problems




- A new way of performing computations by using light -


Useful properties of light

  • light has a limited speed,
  • due to the massive parallelism, light rays can be divided into 2 subrays of smaller intensity.

Basic ideas

Optical computing devices are very simple having a graph-like structure. Each device usually has a start node (where the light enters) and a destination node (where the light is expected to come out).

The light is marked in each node or in each arc so that it can be easily identified at the destination node.

The "marking" operation can be implemented by delaying the light by a certain amount of time. A delay can be obtained by forcing the ray to pass through a cable of a given length.

Later, each ray of light is divided into several small rays which are sent to the outgoing links. This operation can be implemented by using several beam-splitters (half silvered mirrors).

At the destination node we will search for a particular ray which have a particular property required by the problem. This operation can be done easily due to the special properties of the system which delays the rays passing through a node.

Problems that have been solved by using this idea


Some problems can be solved faster than standard computers.


The required amount of energy is exponential. Note that this difficulty is not specific to our system only. Other major unconventional computation paradigms, trying to solve NP-complete problems share the same fate. For instance, a quantity of DNA equal to the mass of Earth is required to solve Hamiltonian Path problem with 200 cities using DNA computers


Home | Description | Links | People | Papers | Grants | Conferences | Theses | Videos

This site was last updated 12/28/07