Solving SAT and Hamiltonian Cycle Problem Using Asynchronous P Systems
-
- TAGAWA Hirofumi
- NTT Data Corporation
-
- FUJIWARA Akihiro
- Kyushu Institute of Technology
この論文をさがす
説明
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.
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E95-D (3), 746-754, 2012
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001204378419072
-
- NII論文ID
- 10030611548
-
- NII書誌ID
- AA10826272
-
- BIBCODE
- 2012IEITI..95..746T
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- 資料種別
- journal article
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可
