Minimal reversible circuit synthesis on a DNA computer

DNA computing has attracted the attention of many a researcher in recent years for its applicability to solve computationally hard problems. It can over-perform conventional computers with its inherent massively parallelism nature. On the other hand, proper synthesis of reversible circuit is a well researched computing problem in recent days for its extremely low power consumption (ideally zero) and inherent reversible nature of reversible logic. Minimum synthesis of a reversible truth table means finding the reversible circuit made up of reversible gates satisfying given truth table with minimum cost. But none of the approaches running on conventional computers can perform minimum synthesis till date without using brute-force DFS tree search. On the other hand, DFS tree-search approach can not be reasonably implemented for larger circuits as searching a DFS tree is extremely costly on a conventional computer. In this paper, first, a procedure to search a DFS tree in constant time has been proposed to run on a DNA computer. Second, another procedure has also been proposed to apply a reversible gate on a reversible truth table in linear time that can be used to generate a DFS tree library. Finally, the generated library can then be searched in constant time to get minimum reversible circuit given a reversible truth table. An analytical feasibility study has been done and a novel methodology has been developed that can extend enormous scope of future research in this area. To the best of authors’ knowledge this is a pioneering approach to bridge reversible computing and DNA computing.