Search

The search for new mechanisms and tools allowing us to tackle the famous P versus NP problem from new perspectives is an important task, due to the relevance of that problem. The concept of efficiency of computing models is associated with the ability to solve intractable (in a classical sense) problems in polynomial time. Assuming that P ≠ NP , that concept is equivalent to the capability to solve NP -complete problems in an efficient way. Different frontiers of the efficiency have been given in Membrane Computing in terms of syntactical or semantic ingredients of the models. In particular, in the framework of tissue P systems with cell division using symport/antiport rules, the length of communication rules (passing from length 1 to length 2) provides an optimal borderline of the efficiency. Cell-like P systems with symport/antiport rules and membrane division is a restricted variant of such tissue P systems in both its structure (rooted tree versus undirected graph) and in the way membranes communicate with each other and with the environment. The limitations of efficient computations in such kind of P systems which use non-cooperative communication rules have been previously established. In this paper, a uniform polynomial time solution for the Hamiltonian cycle problem , a well known NP -complete problem, by means of cell-like P systems with membrane division using minimal cooperation in communication rules (at most two objects are involved), is provided. Hence, a new optimal boundary between tractability and NP -hardness, is provided: passing from non-cooperative rules to cooperative rules in cell-like P systems with symport/antiport rules and membrane division amounts to passing from non-efficiency to efficiency. [ABSTRACT FROM AUTHOR]

Cell division is a process that produces two or more cells from one cell by replicating the original chromosomes so that each daughter cell gets a copy of them. Membrane fission is a process by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane get distributed or separated among the new membranes. Inspired by these biological phenomena, new kinds of models were considered in the discipline of Membrane Computing , in the context of P systems with active membranes, and tissue P systems that use symport/antiport rules, respectively. This paper combines the two approaches: cell-like P systems with symport/antiport rules and membrane separation are studied, from a computational complexity perspective. Specifically, the role of the environment in the context of cell-like P systems with membrane separation is established, and additional borderlines between tractability and NP -hardness are summarized. [ABSTRACT FROM AUTHOR]

P systems with active membranes is one of the most studied models within the field of Membrane Computing. Simulating the organization and behavior of the living cells through a tree-like structure and abstracting the mechanisms that help the cell to keep alive into rules (evolution, communication, dissolution and division rules), they have been used to solve several computationally hard problems. We are dealing with non-cooperative systems here, that is, the number of reactives in a rule is always one. Even then, it has been proven that problems from the class PSPACE can be solved, so in order to acquire a minimal model that can solve computationally hard problems, polarizations are removed. In this paper we find the relevance of the length of the right-hand side of the rule, being necessary when using separation rules and being irrelevant when division rules are used, improving some solutions previously presented, restricting the right-hand side of the rules, obtaining new frontiers of efficiency in this framework. The state of the art of these systems is presented in a graphical way. [ABSTRACT FROM AUTHOR]

P systems with active membranes use evolution, communication, dissolution and division (or separation) rules. They do not use cooperation neither priorities, but they have electrical charges associated with membranes, which can be modified by rule applications. The inspiration comes from the behaviour of living cells, who “compute” with their proteins in order to obtain energy, create components, send information to other cells, kill themselves (in a process called apoptosis ), and so on. In these models, mitosis is simulated by division rules (for elementary and non-elementary membranes) and meiosis , that is, membrane fission inspiration, is captured in separation rules. The parent's objects are replicated into both child membranes when a division occurs, while in the case of separation, objects are distributed (according to a prefixed partition). In both cases, active membranes have been proved to be too powerful for solving computationally hard problems in an efficient way. Due to this, polarizationless P systems with active membranes have been widely studied from a complexity point of view. Evolution rules simulate the transformation of components in membranes, but it is well known that in Biology elements interact with each other in order to obtain new components. In this paper, (restricted) cooperation in object evolution rules is considered, and the efficiency of the corresponding models is studied. [ABSTRACT FROM AUTHOR]

Fuzzy clustering problem is usually posed as an optimization problem. However, the existing research has shown that clustering technique that optimizes a single cluster validity index may not provide satisfactory results on different kinds of data sets. This paper proposes a multiobjective clustering framework for fuzzy clustering, in which a tissue-like membrane system with a special cell structure is designed to integrate a non-dominated sorting technique and a modified differential evolution mechanism. Based on the multiobjective clustering framework, a fuzzy clustering approach is realized to optimize three cluster validity indices that can capture different characteristics. The proposed approach is evaluated on six artificial and ten real-life data sets and is compared with several multiobjective and singleobjective techniques. The comparison results demonstrate the effectiveness and advantage of the proposed approach on clustering the data sets with different characteristics. [ABSTRACT FROM AUTHOR]

Abstract: Several examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems. [Copyright &y& Elsevier]