Solving the subset sum problem with a nonideal biological computer
Konopik, Michael ; Korten, Till ; Linke, Heiner LU
and Lutz, Eric
(2021)
In New Journal of Physics
23(9).
- Abstract
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... (More)
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.
(Less)
- author
- Konopik, Michael
; Korten, Till
; Linke, Heiner
LU
and Lutz, Eric
- organization
- publishing date
- 2021-09
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- biological computation, parallel computation, subset sum problem
- in
- New Journal of Physics
- volume
- 23
- issue
- 9
- article number
- 095007
- publisher
- IOP Publishing
- external identifiers
-
- scopus:85116117659
- ISSN
- 1367-2630
- DOI
- 10.1088/1367-2630/ac2005
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2021 The Author(s). Published by IOP Publishing Ltd on behalf of the Institute of Physics and Deutsche Physikalische Gesellschaft.
- id
- 1ca6e35c-5884-4e8e-bb08-22c3d8d4b547
- date added to LUP
- 2021-10-13 14:27:37
- date last changed
- 2023-11-08 21:13:01
@article{1ca6e35c-5884-4e8e-bb08-22c3d8d4b547,
abstract = {{<p>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.</p>}},
author = {{Konopik, Michael and Korten, Till and Linke, Heiner and Lutz, Eric}},
issn = {{1367-2630}},
keywords = {{biological computation; parallel computation; subset sum problem}},
language = {{eng}},
number = {{9}},
publisher = {{IOP Publishing}},
series = {{New Journal of Physics}},
title = {{Solving the subset sum problem with a nonideal biological computer}},
url = {{http://dx.doi.org/10.1088/1367-2630/ac2005}},
doi = {{10.1088/1367-2630/ac2005}},
volume = {{23}},
year = {{2021}},
}