Journal
JOURNAL OF MEMBRANE COMPUTING
Volume 2, Issue 2, Pages 108-120Publisher
SPRINGERNATURE
DOI: 10.1007/s41965-020-00040-4
Keywords
Membrane computing; Distributed P systems; SAT; Communication complexity
Categories
Funding
- DOST-ERDT project
- UPD - OVCRD 2019-2020
- Semirara Mining Corp.
Ask authors/readers for more resources
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.
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