Solving the subset sum problem with a nonideal biological computer
We consider the solution of the subset sum problem based on a parallel computer consisting of self-propelled biological agents moving in a nanostructured network that encodes the computing task in its geometry. We develop an approximate analytical method to analyze the effects of small errors in the...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2021-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/ac2005 |
| _version_ | 1797750077289136128 |
|---|---|
| author | Michael Konopik Till Korten Heiner Linke Eric Lutz |
| author_facet | Michael Konopik Till Korten Heiner Linke Eric Lutz |
| author_sort | Michael Konopik |
| collection | DOAJ |
| description | We consider the solution of the subset sum problem based on a parallel computer consisting of self-propelled biological agents moving in a nanostructured network that encodes the computing task in its geometry. We develop an approximate analytical method to analyze the effects of small errors in the nonideal junctions composing the computing network by using a Gaussian confidence interval approximation of the multinomial distribution. We concretely evaluate the probability distribution for error-induced paths and determine the minimal number of agents required to obtain a proper solution. We finally validate our theoretical results with exact numerical simulations of the subset sum problem for different set sizes and error probabilities, and discuss the scalability of the nonideal problem using realistic experimental error probabilities. |
| first_indexed | 2024-03-12T16:28:30Z |
| format | Article |
| id | doaj.art-758581293d5949c6ab7cffa57c1799a4 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:28:30Z |
| publishDate | 2021-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-758581293d5949c6ab7cffa57c1799a42023-08-08T15:38:07ZengIOP PublishingNew Journal of Physics1367-26302021-01-0123909500710.1088/1367-2630/ac2005Solving the subset sum problem with a nonideal biological computerMichael Konopik0Till Korten1Heiner Linke2Eric Lutz3https://orcid.org/0000-0002-6176-4229Institute for Theoretical Physics I, University of Stuttgart , D-70550 Stuttgart, GermanyB CUBE-Center for Molecular Bioengineering, Technische Universität Dresden , 01069 Dresden, GermanyNanoLund and Solid State Physics, Lund University , S-22100 Lund, SwedenInstitute for Theoretical Physics I, University of Stuttgart , D-70550 Stuttgart, GermanyWe consider the solution of the subset sum problem based on a parallel computer consisting of self-propelled biological agents moving in a nanostructured network that encodes the computing task in its geometry. We develop an approximate analytical method to analyze the effects of small errors in the nonideal junctions composing the computing network by using a Gaussian confidence interval approximation of the multinomial distribution. We concretely evaluate the probability distribution for error-induced paths and determine the minimal number of agents required to obtain a proper solution. We finally validate our theoretical results with exact numerical simulations of the subset sum problem for different set sizes and error probabilities, and discuss the scalability of the nonideal problem using realistic experimental error probabilities.https://doi.org/10.1088/1367-2630/ac2005biological computationparallel computationsubset sum problem |
| spellingShingle | Michael Konopik Till Korten Heiner Linke Eric Lutz Solving the subset sum problem with a nonideal biological computer New Journal of Physics biological computation parallel computation subset sum problem |
| title | Solving the subset sum problem with a nonideal biological computer |
| title_full | Solving the subset sum problem with a nonideal biological computer |
| title_fullStr | Solving the subset sum problem with a nonideal biological computer |
| title_full_unstemmed | Solving the subset sum problem with a nonideal biological computer |
| title_short | Solving the subset sum problem with a nonideal biological computer |
| title_sort | solving the subset sum problem with a nonideal biological computer |
| topic | biological computation parallel computation subset sum problem |
| url | https://doi.org/10.1088/1367-2630/ac2005 |
| work_keys_str_mv | AT michaelkonopik solvingthesubsetsumproblemwithanonidealbiologicalcomputer AT tillkorten solvingthesubsetsumproblemwithanonidealbiologicalcomputer AT heinerlinke solvingthesubsetsumproblemwithanonidealbiologicalcomputer AT ericlutz solvingthesubsetsumproblemwithanonidealbiologicalcomputer |