Journal
THEORETICAL COMPUTER SCIENCE
Volume 964, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.113976
Keywords
SAT; Membrane computing; Distributed P systems
Categories
Ask authors/readers for more resources
In this study, a string rewriting P system with communication by request is used to solve the satisfiability problem (SAT). The solutions derived from this class of rewriting P system are shown to be uniform in terms of the number of clauses and variables in the input boolean formula. This rewriting P system is then utilized as components in constructing a distributed P system that solves SAT. It is demonstrated that encoding the truth assignment for the communication steps only requires a polynomial number of rules, but achieving a low communication cost requires an exponential-sized set of inter-component communication rules.
In this study, string rewriting P systems with communication by request is used in solving the satisfiability problem, or SAT. The family of solutions using this class of rewriting P system is shown to be uniform, in terms of the number of clauses and variables of the input boolean formula. This rewriting P system is then used as components for the construction of a distributed P system solving SAT. It is shown in this work that encoding the truth assignment for the communication steps only require a polynomial number of rules to implement, but requires an exponential-sized set of inter-component communication rules to achieve a low communication cost. & COPY; 2023 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available