Solving the subset-sum problem with a light-based device

DOI10.1007/S11047-007-9059-3MaRDI QIDQ1024028zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mihai Oltean, Oana Muntean

Publication date 16 June 2009

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.1964

zbMATH Keywords

NP-completeoptical solutionssubset sumunconventional computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: We propose a special computational device which uses light rays for solving the subset-sum problem. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible subsets of the given set. To each arc we assign either a number from the given set or a predefined constant. When the light is passing through an arc it is delayed by the amount of time indicated by the number placed in that arc. At the destination node we will check if there is a ray whose total delay is equal to the target value of the subset sum problem (plus some constants).

Recommendations

• Solving the generalized subset sum problem with a light based device
• An optical solution for the set splitting problem
• Exact cover with light
• Solving the Hamiltonian path problem with a light-based computer
• A Light-Based Device for Solving the Hamiltonian Path Problem

Cites work

• A Light-Based Device for Solving the Hamiltonian Path Problem
• An optical model of computation
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 743584 (Why is no real title available?)
• Multistage Cutting Stock Problems of Two and More Dimensions
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for Hilbert's tenth problem
• Rainbow sort: Sorting at the speed of light
• Solving the Hamiltonian path problem with a light-based computer
• The complexity of analog computation

Cited in

(9)

• An optical solution for the set splitting problem
• On the computational power of the light: a plan for breaking data encryption standard
• On the complexity of nonuniform wavelength-based machine
• Solving the generalized subset sum problem with a light based device
• The Traveling Beams Optical Solutions for Bounded NP-Complete Problems
• A Light-Based Device for Solving the Hamiltonian Path Problem
• Exact cover with light
• Masking traveling beams: optical solutions for NP-complete problems, trading space for time
• Solving the Hamiltonian path problem with a light-based computer

This page was built for publication: Solving the subset-sum problem with a light-based device

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024028)