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. |
Year | Venue | Keywords |
---|---|---|
2006 | FCS | max-sat,dna strands. keywords: dna computing,optimization problem,boolean function,dna computing |
Field | DocType | Citations |
Boolean function,Complementarity (molecular biology),Maximum satisfiability problem,Brute-force search,Polynomial,Algorithm,Theoretical computer science,Hamiltonian path problem,Boolean data type,Mathematics,DNA computing | Conference | 0 |
PageRank | References | Authors |
0.34 | 8 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuichiro Tokumaru | 1 | 0 | 0.68 |
Akihiro Fujiwara | 2 | 122 | 27.25 |