Solving the subset sum problem using distributed tissue-like P systems with cell division / Justin Granda, Samuel Jose and Kelvin Cui Buño.

The Subset Sum Problem is a decision problem where given a multiset of integers, a decision must be made on whether a subset of said set can be found where the sum of its elements is equal to a target value, or not. This problem is NP-Complete. Membrane computing is one of the ways used to approach these problems, using a computing model commonly referred to as P systems. In this work, we solve the Subset Sum Problem using dP systems where the components are tissue P systems with cell division. The 2-component solution proposed can generate candidate solutions twice as fast, as compared to the non-distributed solution it was based on. However, computation time is increased with respect to the target sum. Communication costs are analyzed and measured.