Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
The Traveling Beams Optical Solutions for Bounded NP-Complete Problems
(Extended Abstract)
verfasst von : Shlomi Dolev, Hen Fitoussi
Erschienen in: Fun with Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Architectures for optical processors designed to solve bounded instances of NP-Complete problems are suggested. One approach mimics the traveling salesman by traveling beams that simultaneously examine the different possible paths. The other approach uses a pre-processing stage in which
O
(
n
2
) masks are constructed, each representing a different edge in the graph. The choice and combination of the appropriate (small) subset of these masks yields the solution. The solution is rejected in cases where the combination of these masks totally blocks the light and accepted otherwise. We present detailed designs for basic primitives of the optical processor. We propose designs for solving Hamiltonian path, Traveling Salesman, Clique, Independent Set, Vertex Cover, Partition, 3-SAT, and 3D-matching.