Asynchronous P systems for SAT and Hamiltonian cycle problem

In the present paper, we consider the asynchronous parallelism in membrane computing, and propose fully asynchronous P systems such that any number of applicable rules may be applied in one step. Since there is no restrictive assumption for application of rules, sequential and maximal parallel executions are allowed on the asynchronous P system. We 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(mn2ⁿ) 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(n²) parallel steps using O(n²) kinds of objects.