# 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.

## 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