Optical solutions to NP-Complete problems

Home
Description
Papers
Conferences
People
Videos

The purpose of this research is to use light and other signals to perform computations. Several devices for solving NP-complete problems have been proposed. This kind of solving problems is also called computation with time-delays.

Here are some properties of light useful for our system:

  • light has a limited speed, and thus we can delay it
  • due to the massive parallelism, light rays can be divided into 2 (sub)rays 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/signal enters) and a destination node (where the light/signal 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. Sometime this way to solve problems is also called computations with time-delays.

  • 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:

Strengths

On some problems it can be faster than digital computers.

Weaknesses

The required amount of energy is exponential.

Note that this difficulty is not specific to this 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

Video: Optical computing for the subset sum problem