DNA-Based Computing of Strategic Assignment Problems

DNA-based computing is a novel technique to tackle computationally difficult problems, in which computing time grows exponentially corresponding to problematic size. A strategic assignment problem is a typical nondeterministic polynomial problem, which is often associated with strategy applications. In this Letter, a new approach dealing with strategic assignment problems is proposed based on manipulating DNA strands, which is believed to be better than the conventional silicon-based computing in solving the same problem.

Figure 1

Bipartite graph of Tian Ji’s horse racing.

Figure 2

Strategic assignment problem: (a) bipartite graph and (b) complementary graph, which connects vertices that are absent in (a).

Figure 3

Path DNA sequence.