nach oben

Natural Computing

Erschienen in:

01.06.2009

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

verfasst von: Mihai Oltean, Oana Muntean

Erschienen in: Natural Computing | Ausgabe 2/2009

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We propose an optical 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). The proposed optical solution solves a NP-complete problem in time proportional with the target sum, but requires an exponential amount of energy.

Vorheriger Artikel Negative correlation in incremental learning

Nächster Artikel Successful preparation and analysis of a 5-site 2-variable DNA library

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

Aaronson S (2005) NP-complete problems and physical reality, ACM SIGACT News Complexity Theory Column, March. ECCC TR05-026, quant-ph/0502072

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

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

Bajcsy M, Zibrov AS, Lukin MD (2003) Stationary pulses of light in an atomic medium. Nature 426:638–641CrossRef

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

Cormen TH, Leiserson CE, Rivest RR (1990) Introduction to algorithms. MIT Press

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

Feitelson DG (1988) Optical computing: a survey for computer scientists, MIT Press

Flyckt SO, Marmonier C (2002) Photomultiplier tubes: principles and applications. Photonis, Brive, France

Garey MR, Johnson DS (1979) Computers and intractability: a guide to NP-completeness. Freeman & Co, San Francisco, CAMATH

Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13(1):94–120MATHCrossRef

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

Haist T and Osten W (2007) An optical solution for the traveling salesman problem. Opt Express 15:10473–10482CrossRef

Hartmanis J (1995) On the weight of computations. B EATCS 55:136–138MATH

Hau LV, Harris SE, Dutton Z, Behroozi CH (1999) Light speed reduction to 17 m per second in an ultracold atomic gas. Nature 397:594–598CrossRef

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

Lenslet website (2005) http://www.lenslet.com

Liu C, Dutton Z, Behroozi CH, Hau LV (2001) Observation of coherent optical information storage in an atomic medium using halted light pulses. Nature 409:490–493CrossRef

Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, van der Burgt PJM, Woods N (2006) Implementations of a model of physical sorting. In: Adamatzky A, Teuscher C (eds) From Utopian to genuine unconventional computers workshop, Luniver Press, pp 79–100

Naughton TJ (2000) A model of computation for Fourier optical processors. In: Lessard RA, Galstian T (eds) Optics in computing, Proceedings SPIE 4089:24–34

Oltean M (2006) A light-based device for solving the Hamiltonian path problem. In: Calude C et al (eds) Unconventional computing LNCS 4135, Springer-Verlag, pp 217–227

Oltean M (2007) Solving the Hamiltonian path problem with a light-based computer. Nat Comput doi:10.1007/s11047-007-9042-z

Paniccia M, Koehl S (2005) The silicon solution. IEEE Spectrum, IEEE Press, October

Reif JH, Tyagi A (1997) Efficient parallel algorithms for optical computing with the discrete Fourier transform primitive. Appl Optics 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 (2005) Rainbow Sort: sorting at the speed of light. Nat Comput, Springer-Verlag 5(1):67–82

Shaked NT, Messika S, Dolev S and Rosen J (2007) Optical solution for bounded NP-complete problems. Appl Optics 46:711–724CrossRef

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

Thoughts on the subset sum problem (P vs. NP) (accessed 2006) http://idrone.net/2006/06/11/thoughts-on-the-subset-sum-problem-p-vs-np

Vergis A, Steiglitz K, Dickinson B (1986) The complexity of analog computation. Math Comput Simulat 28:91–113MATHCrossRef

Woods D, Naughton TJ (2005) An optical model of computation. Theor Comput Sci 334 (1–3):227–258MATHCrossRefMathSciNet

Titel: Solving the subset-sum problem with a light-based device
verfasst von: Mihai Oltean
Oana Muntean
Publikationsdatum: 01.06.2009
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2009
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-007-9059-3

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 2/2009

Integrative connectionist learning systems inspired by nature: current models, future trends and challenges

A survey on metaheuristics for stochastic combinatorial optimization

A framework for machine learning based on dynamic physical fields

Competition and evolution in virtual plant communities: a new modeling approach

Successful preparation and analysis of a 5-site 2-variable DNA library

Negative correlation in incremental learning

Premium Partner