Using DNA to solve the Bounded Post Correspondence Problem

摘要

Theoretical research in DNA computing includes designing practical experiments for solving various computational problems by means of DNA manipulation. This paper proposes a DNA algorithm for an NP-complete problem, The Bounded Post Correspondence Problem. The proposed experiment can be used to test several standard molecular biology laboratory procedures for their usability as bio-operations in DNA computing. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 54]