School News

NP Complete Problems
Dr. Tony McCaffrey, Computer Science Teacher

A New Bio-Computer Designed by EHS Computer Science Teacher

Dr. McCaffrey uses synthetic biology bio-computing to solve NP-Complete problems.

Dr. Tony McCaffrey is interdisciplinary by nature. His advanced degrees are in computer science, psychology, neuroscience, philosophy, and theology. He usually looks for gaps between disciplines and tries to find new things that will emerge from bringing together those disciplines.

His latest research result has been accepted by a synthetic biology conference and he will be presenting it on May 5th in Arlington, Virginia (2022 Synthetic Biology Conference). Synthetic biology is widely interdisciplinary covering many fields, which include biotechnology, genetic engineering, molecular biology and engineering, chemical engineering, electrical and computer engineering, and evolutionary biology.

McCaffrey brings to synthetic biology his background in computer programming, computer engineering, artificial intelligence, algorithm analysis, and complexity theory. His co-author, Professor Thomas Gorochowski, University of Bristol, UK, brings his expertise in many areas of the biological sciences.

Their paper presents a new design for a bio-computer that is very different than other designs that try to bring together biology and computer architecture. Most bio-computing researchers try to recreate in biology the logic gates that have been so successful in silicon computer designs. However, logic gates implemented in bio-matter are not as reliable and robust as their silicon counterparts.

Further, silicon designs currently use a binary representation (1s and 0s). McCaffrey uses a different a non-binary coding scheme that can be more efficiently manipulated in many biological materials.

The fun result of the paper is that biology can now efficiently solve what are called NP-Complete problems, which are problems that have no known efficient solutions. By leveraging certain features of biological material, McCaffrey’s algorithms can solve these very difficult problems in a highly efficient manner. Further, the entire set of NP-Complete problems all suffer from the same obstacle that makes their known solutions inefficient. However, if you can efficiently solve one of the NP-Complete problems, you can efficiently solve all of them. They are either all highly inefficient or all highly efficient.

Quantum computing is in vogue these days as the future of computing. Trillions of dollars of research and investment monies have been poured into making quantum computing the future of both efficient computing, as well as encryption. McCaffrey, who likes underdogs, decided to research the less-hyped area of bio-computing. With McCaffrey’s new algorithms and Gorochowski’s ideas for how to implement them in bio-material, bio-computing might sneak up on and pass quantum computing to become the real future of computing.

Leave a Comment

We'd love to hear from you!  Please send us a message.

Required

Namerequired
First Name
Last Name