期刊
THEORETICAL COMPUTER SCIENCE
卷 964, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.113976
关键词
SAT; Membrane computing; Distributed P systems
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据