Solving SAT and Hamiltonian Cycle Problem Using Asynchronous P Systems

スポンサーリンク

概要

• 論文の詳細を見る

• In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose two asynchronous P systems for the satisfiability (SAT) and Hamiltonian cycle problem. We first propose an asynchronous P system that solves SAT with n variables and m clauses, and show that the proposed P system computes SAT in O(mn2n) sequential steps or O(mn) parallel steps using O(mn) kinds of objects. We next propose an asynchronous P system that solves the Hamiltonian cycle problem with n nodes, and show that the proposed P system computes the problem in O(n!) sequential steps or O(n2) parallel steps using O(n2) kinds of objects.

• The Institute of Electronics, Information and Communication Engineersの論文
• 2012-03-01

著者

• Fujiwara Akihiro

  Kyushu Institute of Technology

• Tagawa Hirofumi

  Ntt Data Corporation

関連論文

• Special Section on Parallel/Distributed Processing and Systems
• A-16 Addressable Procedures for Logic and Arithmetic Operations with DNA Strands
• Solving SAT and Hamiltonian Cycle Problem Using Asynchronous P Systems

スポンサーリンク