Please note: This PhD seminar will be given online.
Zihao Wang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Lila Kari
Some DNA computing approaches have been proposed to solve NP-complete problems in polynomial time with some trade-offs, such as having an exponential number of computing agents, and some were realized in a proof-of-concept experiment. The network biocomputing method is another example of a non-conventional approach to NP-complete problems. Regardless of the fundamental differences between these methods, we can compare their time, space and energy complexities. For the comparison, the subset sum problem is chosen as the benchmark problem, and different problem sizes and types of input sets are considered. In brief, the advantages of the DNA computing approach to the subset sum problem include the polynomial growth of the computing time. In contrast, the benefits of the network biocomputing approach include the smaller amount of required computing agents.