Solving SAT and Hamiltonian Cycle Problem Using Asynchronous P Systems

DOI Web Site BIBCODE 被引用文献6件 参考文献23件

この論文をさがす

抄録

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.

収録刊行物

被引用文献 (6)*注記

もっと見る

参考文献 (23)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ