Solving the SAT Problem by Cell-Like P Systems with Channel States and Symport Rules

Xiaoming Wan, Chuchuan Liu, Yueguo Luo and Ya Jia

Discrete Dynamics in Nature and Society, 2023, vol. 2023, 1-9

Abstract: Cell-like P systems with channel states, which are a variant of tissue P systems in membrane computing, can be viewed as highly parallel computing devices based on the nested structure of cells, where communication rules are classified as symport rules and antiport rules. In this work, we remove the antiport rules and construct a novel variant, namely, cell-like P systems with channel states and symport rules, where one rule is only allowed to be nondeterministically applied once per channel. To explore the computational efficiency of the variant, we solve the SAT problem and obtain a uniform solution in polynomial time with the maximal length of rules 1. The results of our work are reflected in the following two aspects: first, communication rules are restricted to only one type, namely, symport rules; second, the maximal length of rules is decreased from 2 to 1. Our work indicates that the constructed variant with fewer rule types can still solve the SAT problem and obtain better results in terms of computational complexity. Hence, in terms of computational efficiency, our work is a notable improvement.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2023/4993855.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2023/4993855.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:4993855

DOI: 10.1155/2023/4993855

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().