A Polynomial-Time DNA Computing Solution for the N-Queens Problem

详细信息    查看全文

• 作者：Ramin Maazallahi ; Aliakbar Niknafs ; Paria Arabkhedri
• 关键词：DNA computing ; Adleman-Lipton Model ; N-queens problem ; NP-Complete
• 刊名：Procedia - Social and Behavioral Sciences
• 出版年：2013
• 出版时间：4 July, 2013
• 年：2013
• 卷：83
• 期：Complete
• 页码：622-628
• 全文大小：954 K

文摘

The N-queens problem is a classic combinatorial problem that there is no polynomial time solution for it in silicon based computers. It belongs to the set of NP-Complete problems and needs a plenty of calculations. On the other hand, it has been evidenced that DNA computing is able to solve such complex problems efficiently. In this paper we propose a method based on Adleman-Lipton model, a model of DNA computing, which is able to solve the N-queens problem in a polynomial time complexity. It provides all the solutions and runs in O(N²).