As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem
All known algorithms to solve nondeterministic polynomial (NP) complete problems, relevant to many real-life applications, require the exploration of a space of potential solutions, which grows exponentially with the size of the problem. Since electronic computers can implement only limited parallel...
| 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/ac3883 |
| _version_ | 1827872649591652352 |
|---|---|
| author | Ayyappasamy Sudalaiyadum Perumal Zihao Wang Giulia Ippoliti Falco C M J M van Delft Lila Kari Dan V Nicolau |
| author_facet | Ayyappasamy Sudalaiyadum Perumal Zihao Wang Giulia Ippoliti Falco C M J M van Delft Lila Kari Dan V Nicolau |
| author_sort | Ayyappasamy Sudalaiyadum Perumal |
| collection | DOAJ |
| description | All known algorithms to solve nondeterministic polynomial (NP) complete problems, relevant to many real-life applications, require the exploration of a space of potential solutions, which grows exponentially with the size of the problem. Since electronic computers can implement only limited parallelism, their use for solving NP-complete problems is impractical for very large instances, and consequently alternative massively parallel computing approaches were proposed to address this challenge. We present a scaling analysis of two such alternative computing approaches, DNA computing (DNA-C) and network biocomputing with agents (NB-C), compared with electronic computing (E-C). The Subset Sum Problem (SSP), a known NP-complete problem, was used as a computational benchmark, to compare the volume, the computing time, and the energy required for each type of computation, relative to the input size. Our analysis shows that the sequentiality of E-C translates in a very small volume compared to that required by DNA-C and NB-C, at the cost of the E-C computing time being outperformed first by DNA-C (linear run time), followed by NB-C. Finally, NB-C appears to be more energy-efficient than DNA-C for some types of input sets, while being less energy-efficient for others, with E-C being always an order of magnitude less energy efficient than DNA-C. This scaling study suggest that presently none of these computing approaches win, even theoretically, for all three key performance criteria, and that all require breakthroughs to overcome their limitations, with potential solutions including hybrid computing approaches. |
| first_indexed | 2024-03-12T16:26:49Z |
| format | Article |
| id | doaj.art-c633c37944f04241a37725c01be95e9b |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:26:49Z |
| publishDate | 2021-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-c633c37944f04241a37725c01be95e9b2023-08-08T15:42:02ZengIOP PublishingNew Journal of Physics1367-26302021-01-01231212500110.1088/1367-2630/ac3883As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problemAyyappasamy Sudalaiyadum Perumal0https://orcid.org/0000-0002-1360-9152Zihao Wang1Giulia Ippoliti2Falco C M J M van Delft3https://orcid.org/0000-0002-3234-2211Lila Kari4Dan V Nicolau5https://orcid.org/0000-0002-9956-0600Department of Bioengineering, McGill University , Montreal, CanadaSchool of Computer Science, University of Waterloo , Waterloo, CanadaDepartment of Bioengineering, McGill University , Montreal, CanadaMolecular Sense Ltd , Liverpool, United KingdomSchool of Computer Science, University of Waterloo , Waterloo, CanadaDepartment of Bioengineering, McGill University , Montreal, CanadaAll known algorithms to solve nondeterministic polynomial (NP) complete problems, relevant to many real-life applications, require the exploration of a space of potential solutions, which grows exponentially with the size of the problem. Since electronic computers can implement only limited parallelism, their use for solving NP-complete problems is impractical for very large instances, and consequently alternative massively parallel computing approaches were proposed to address this challenge. We present a scaling analysis of two such alternative computing approaches, DNA computing (DNA-C) and network biocomputing with agents (NB-C), compared with electronic computing (E-C). The Subset Sum Problem (SSP), a known NP-complete problem, was used as a computational benchmark, to compare the volume, the computing time, and the energy required for each type of computation, relative to the input size. Our analysis shows that the sequentiality of E-C translates in a very small volume compared to that required by DNA-C and NB-C, at the cost of the E-C computing time being outperformed first by DNA-C (linear run time), followed by NB-C. Finally, NB-C appears to be more energy-efficient than DNA-C for some types of input sets, while being less energy-efficient for others, with E-C being always an order of magnitude less energy efficient than DNA-C. This scaling study suggest that presently none of these computing approaches win, even theoretically, for all three key performance criteria, and that all require breakthroughs to overcome their limitations, with potential solutions including hybrid computing approaches.https://doi.org/10.1088/1367-2630/ac3883unconventional computingnatural computingDNA computingnetwork biocomputingNP-complete problemsubset sum problem |
| spellingShingle | Ayyappasamy Sudalaiyadum Perumal Zihao Wang Giulia Ippoliti Falco C M J M van Delft Lila Kari Dan V Nicolau As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem New Journal of Physics unconventional computing natural computing DNA computing network biocomputing NP-complete problem subset sum problem |
| title | As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem |
| title_full | As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem |
| title_fullStr | As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem |
| title_full_unstemmed | As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem |
| title_short | As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem |
| title_sort | as good as it gets a scaling comparison of dna computing network biocomputing and electronic computing approaches to an np complete problem |
| topic | unconventional computing natural computing DNA computing network biocomputing NP-complete problem subset sum problem |
| url | https://doi.org/10.1088/1367-2630/ac3883 |
| work_keys_str_mv | AT ayyappasamysudalaiyadumperumal asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem AT zihaowang asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem AT giuliaippoliti asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem AT falcocmjmvandelft asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem AT lilakari asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem AT danvnicolau asgoodasitgetsascalingcomparisonofdnacomputingnetworkbiocomputingandelectroniccomputingapproachestoannpcompleteproblem |