nach oben

Natural Computing

Erschienen in:

01.03.2011

Solving the generalized Subset Sum problem with a light based device

verfasst von: Masud Hasan, Shabab Hossain, Md. Mahmudur Rahman, M. Sohel Rahman

Erschienen in: Natural Computing | Ausgabe 1/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recently, a number of researchers have suggested light-based devices to solve combinatorially interesting problems. In this paper, we design a light based device to solve a generalized version of the Subset Sum problem which was previously handled by Oltean and Muntean. We further design a system which is capable of providing us with the solution subset of the problem in addition to the YES/NO answer to the question of whether there exists a solution or not.

Vorheriger Artikel Friction-based sorting

Nächster Artikel Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The answer of the decision problem would be found from the device designed in the previous section.

Aaronson S (2005) Np-complete problems and physical reality. ACM SIGACT News Complexity Theory Column, ECCC TR05-026

Adleman L (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021–1024

Agrawal GP (2002) Fibre-optic communication systems, 3rd edn. Wiley-Interscience, New YorkCrossRef

Bringsjord S, Taylor J (2004) P=np. cs.CC/0406056

Faist J (2005) Optoelectronics: silicon shines on. Nature 433:691–692CrossRef

Feitelson DG (1998) Optical computing: a survey for computer scientists. MIT Press, Cambridge

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New YorkMATH

Goodman JW (1982) Architectural development of optical data processing systems. Aust J Electr Electron Eng 2:139–149

Hasan M, Shabab Hossain SM, Mahmudur Rahman Md, Sohel Rahman M (2009) An optical solution for the subset sum problem. In: Peper F, Umeo H, Matsui N, Isokawa T (eds) Natural computing: 4th international workshop on natural computing. Himeji, Japan, September 2009 Proceedings, pp 165–173

Raqibul Hasan Md, Sohel Rahman M (2009) Computing a solution for the subset sum problem with a light based device. In Dolev S, Oltean M (eds) OSC, vol 5882 of Lecture notes in computer science. Springer, Berlin, pp 70–76

Kieu TD (2003) Quantum algorithm for Hilbert’s tenth problem. Int J Theor Phys 42:1461–1478MathSciNetMATHCrossRef

Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, Burgt PJM, Woods N (2006) Implementations of a model of physical sorting. Luniver Press, Frome, pp 79–100

Oltean M (2008) Solving the Hamiltonian path problem with a light-based computer. Nat Comput 7(1):57–70MathSciNetMATHCrossRef

Oltean M (2009) Light-based string matching. Nat Comput 8(1):121–132MathSciNetMATHCrossRef

Oltean M, Muntean O (2008) Exact cover with light. New Gener Comput 26(4):329–346MATHCrossRef

Oltean M, Muntean O (2009) Solving the subset-sum problem with a light-based device. Nat Comput 8(2):321–331MathSciNetMATHCrossRef

Panicia M, Koehl S (2005) The silicon solution. IEEE Spectrum 42(10):38–43CrossRef

Reif JH, Tyagi A (1997) Efficient parallel algorithms for optical computing with the discrete fourier transform primitive. Appl Opt 36(29):7327–7340CrossRef

Rong H, Jones R, Liu A, Cohen O, Hak D, Fang A, Paniccia M (2005a) A continuous wave Raman silicon laser. Nature 433:725–728CrossRef

Rong H, Liu A, Jones R, Cohen O, Hak D, Nicolaescu R, Fang A, Paniccia M (2005b) An all-silicon Raman laser. Nature 433:292–294CrossRef

Schultes D (2006) Rainbow sort: sorting at the speed of light. Nat Comput 5(1):67–82MathSciNetMATHCrossRef

Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26(5):1484–1509MathSciNetMATHCrossRef

Vergis A, Steiglitz K, Dickinson B (1996) The complexity grave of analog computation. Math Comput Simul 28:91–113CrossRef

Titel: Solving the generalized Subset Sum problem with a light based device
verfasst von: Masud Hasan
Shabab Hossain
Md. Mahmudur Rahman
M. Sohel Rahman
Publikationsdatum: 01.03.2011
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2011
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-010-9205-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2011

Evolutionary and population dynamics of 3 parents differential evolution (3PDE) using self-adaptive tuning methodologies

Editorial for special issue on the interaction between computation and biology

Grammar-based immune programming

NP-completeness of the energy barrier problem without pseudoknots and temporary arcs

DNA chips for species identification and biological phylogenies

Selected papers of Vincenzo Manca

Premium Partner