Parallel computation with molecular-motor-propelled agents in nanofabricated networks.
(2016) In Proceedings of the National Academy of Sciences 113(10). p.2591-2596- Abstract
- The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is... (More)
- The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/8821971
- author
- Nicolau, Dan V ; Lard, Mercy LU ; Korten, Till ; van Delft, Falco C M J M ; Persson, Malin ; Bengtsson, Elina ; Månsson, Alf ; Diez, Stefan and Linke, Heiner LU
- organization
- publishing date
- 2016-02-22
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Proceedings of the National Academy of Sciences
- volume
- 113
- issue
- 10
- pages
- 2591 - 2596
- publisher
- National Academy of Sciences
- external identifiers
-
- pmid:26903637
- scopus:84960532489
- wos:000372013300025
- pmid:26903637
- ISSN
- 1091-6490
- DOI
- 10.1073/pnas.1510825113
- language
- English
- LU publication?
- yes
- id
- 8db589fe-4bdc-4a32-905c-91b93a7423f9 (old id 8821971)
- date added to LUP
- 2016-04-01 10:10:02
- date last changed
- 2023-11-09 12:50:05
@article{8db589fe-4bdc-4a32-905c-91b93a7423f9, abstract = {{The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.}}, author = {{Nicolau, Dan V and Lard, Mercy and Korten, Till and van Delft, Falco C M J M and Persson, Malin and Bengtsson, Elina and Månsson, Alf and Diez, Stefan and Linke, Heiner}}, issn = {{1091-6490}}, language = {{eng}}, month = {{02}}, number = {{10}}, pages = {{2591--2596}}, publisher = {{National Academy of Sciences}}, series = {{Proceedings of the National Academy of Sciences}}, title = {{Parallel computation with molecular-motor-propelled agents in nanofabricated networks.}}, url = {{http://dx.doi.org/10.1073/pnas.1510825113}}, doi = {{10.1073/pnas.1510825113}}, volume = {{113}}, year = {{2016}}, }