Solving 3-SAT in distributed P systems with string objects

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.

Automated summary

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.