期刊
JOURNAL OF MEMBRANE COMPUTING
卷 2, 期 2, 页码 108-120出版社
SPRINGERNATURE
DOI: 10.1007/s41965-020-00040-4
关键词
Membrane computing; Distributed P systems; SAT; Communication complexity
资金
- DOST-ERDT project
- UPD - OVCRD 2019-2020
- Semirara Mining Corp.
In a work presented by Gazdag and Kolonits from 2013, it was shown that SAT can be solved in linear time in the number of variables using the clause completion method on a non-distributed P system with active membranes. A distributed P system with active membranes using the clause completion method solving SAT (denoted as k-Delta (n)) is presented in this work. k-Delta (n) is a weak uniform solution to SAT that runs in linear time with respect only to the number of variables, n, of the Boolean formula phi. For the 2-component solution, 2-Delta (n), we show that the communication cost is constant. But, increasing the number of components in k-Delta (n), k >= 3, would make the communication cost dependent on not just the number of components and the number of variables, but as well as the number of satisfying assignments to phi. We report that an exponential amount of resources (in terms of alphabet size and rules) are necessary to construct k-Delta (n) solving SAT to obtain these reasonable communication costs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据