A procedure for computing 0-1 integer programming with DNA strands

In recent works for high performance computing, computation with DNA molecules, that is, DNA computing, has had considerable attention as one of non-silicon based computing. Using features of DNA molecules, we can solve some NP optimization problems, which usually need exponential time on a silicon based computer, in a polynomial number of steps with DNA molecules. In this paper, we propose a procedure for computing the 0-1 integer programming which is a well-known NP-hard problem. An input of the problem consists of n Boolean variables, h linear constraints and an objective function. Each coefficient or constant is denoted by a binary number of m bits. For the 0-1 integer programming, we propose a procedure which runs in O(n + log h) steps using O ((m + n) 2(n)) DNA strands.