Abstract

There is a class of diverse mathematical complexity problems such as the travelling salesman problem of looking for a shortest possible route on a map, often referred as Nondeterministic Polynomial (NP) complete problems. There is still yet no efficient algorithm to solve these problems within polynomial time by a deterministic Turing machine. Besides the conventional approach with electronic computers, Non-Turing approaches such as DNA, quantum and optical computing may work. Here we show that these NP-complete problems may be solved by using a new type of all-optical computer. A proof-of-principle demonstration was performed on a fiber network representing a map of five towns on the NP-complete directed Hamiltonian path problem of deciding if a map can be travelled in a unidirectional way that each town is visited exactly once. The decision was successfully obtained only in a few tens of nanoseconds. We argue that current fiber technology shall allow interrogating graphs of hundreds of nodes and providing a simple-to-implement alternative to a quantum computer approach.

© 2013 IEEE