Networks of splicing processors with evaluation sets as optimization problems solvers

In this paper we consider a new highly parallel and distributed bio-inspired computational model having its underlying structure an undirected graph whose nodes are processors that use the splicing operation on the data they are processing. They communicate with each other via a protocol based on the compatibility between their accepting values with respect to some predefined evaluation sets and the values of the data computed by a valuation mapping. Here we use the valuation mapping from a quantitative perspective, hence this model might be more suitable to solve some specific hard optimization problems in a more efficient and succinct way. In the aim of supporting this possibility, we propose an algorithm based on these networks able to efficiently solve an NP-hard combinatorial problem, namely the 0/1 knapsack problem. We prove that the computation time of the network solving an instance of the problem is linear. Surprisingly enough, the size of the network is very small, only four nodes are sufficient and the topology of the network may be chosen as chain, ring or complete graph. Furthermore, the evaluation sets and the sets of compatible values associated with the nodes as well as the valuation mapping remain unchanged for all instances of the same size. This result suggests that this model is suitable to address optimization problems where quantitative conditions have a relevant role.