An optical solution for the set splitting problem

DOI10.1515/AUSI-2017-0009MaRDI QIDQ1698573zbMATH OpenOpenAlexFDO

Authors Mihai Oltean

Publication date 16 February 2018

Published in Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

NP-completenessoptical computingset splitting

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: We describe here an optical device, based on time-delays, for solving the set splitting problem which is well-known NP-complete problem. The device has a graph-like structure and the light is traversing it from a start node to a destination node. All possible (potential) paths in the graph are generated and at the destination we will check which one satisfies completely the problem's constrains.

Recommendations

• Solving the subset-sum problem with a light-based device
• The Traveling Beams Optical Solutions for Bounded NP-Complete Problems
• Exact cover with light
• Masking traveling beams: optical solutions for NP-complete problems, trading space for time
• Solving the generalized subset sum problem with a light based device

Cites work

• A Light-Based Device for Solving the Hamiltonian Path Problem
• Computing transparently: The independent sets in a graph
• Exact cover with light
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Light ray concentration reduces the complexity of the wavelength-based machine on PSPACE languages
• Lower bounds on the complexity of the wavelength-based machine
• On the complexity of nonuniform wavelength-based machine
• Solving the subset-sum problem with a light-based device
• The Traveling Beams Optical Solutions for Bounded NP-Complete Problems

Cited in

(6)

• Solving the subset-sum problem with a light-based device
• 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

This page was built for publication: An optical solution for the set splitting problem

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