Distributed computation of a k P systems with active membranes for SAT using clause completion

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.