A procedure for MAX-SAT with DNA strands

Abstract: In recent works for high performance computing, computation with DNA molecules, that is, DNA com-puting, has had considerable attention as one of non-silicon based computing. Using features of DNA molecules, we can solve some 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 MAX-SAT which is a well-known -hard problem. An input of the problem consists of Boolean variables and a Boolean function which has clauses. Each input is denoted by a binary number of bits. For MAX-SAT, we propose a procedure which runs in steps using DNA strands. Since an input of the procedure is prepared in steps using DNA strands, we solve MAX-SAT in steps using DNA strands.