Seeking Sharper Frontiers of Efficiency in Tissue P Systems: in the collective paper, Research frontiers in Membrane Computing: Open problems and research topics.

October 10, 2013 15:33 WSPC/INSTRUCTION FILE S0129054113500202 10. Seeking Sharper Frontiers of Efficiency in Tissue P Systems Mario J. P´erez-Jim´enez1, Agust´ın Riscos-N´u˜nez1, Miquel Rius-Font2 and ´Alvaro Romero-Jim´enez1 1Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] 2Department of Applied Mathematics IV Universitat Polit´ecnica de Catalunya, Casteldefels, Spain [email protected] In a P system, there are several ingredients which influence their efficiency. Varying them, one can get efficient systems (able to solve computationally hard problems in polynomial time) or non-efficient systems (e.g., solving NP-hard problems in an exponential time). The borderline between efficiency and non-efficiency is thus a problem of a central interest. This issue is explored here for tissue P systems. Required Notions: tissue P systems, complexity classes, cell division, cell separation, symport/antiport rule A tissue P system with symport/antiport rules Π = (Γ, E, M1, . . . , Mq , R, iout), of degree q ≥ 1 can be viewed as a set of q cells, labeled by 1, . . . , q, with an environment labeled by 0 which initially have an arbitrary number of copies of some kind of objects, and a set of rules which can be of several types: communication, division or separation (see [3, 4] for details). For each natural number k ≥ 1, TDC(k) (respectively, TDS(k) or TDA(k)) is the class of recognizer tissue P systems with cell division and communication rules (allowing only symport or antiport rules, respectively) of length at most k. Similarly, October 10, 2013 15:33 WSPC/INSTRUCTION FILE S0129054113500202 by considering separation rules instead of division rules, we obtain TSC(k), TSS(k) and TSA(k) respectively. We denote by PMCR the set of all decision problems which can be solved in a uniform way and polynomial time by means of families of systems from a class R of recognizer tissue P systems. (A) Tissue P systems with cell division and with cell separation By using the dependency graph technique, it has been proved that P= PMCT DC(1) =PMCT SC(1) [2,3]. Furthermore, efficient and uniform solutions to the SAT problem by using systems from TDC(3) [1] and from TSC(8) [3] have been given. Recently, the last result has been improved to SAT ∈PMCT SC(3) [6]. Problem 10.1. Assuming P6=NP, in the framework of tissue P systems with cell division/cell separation, a frontier of the tractability is obtained when passing from communication rules with length 1 to communication rules with length at most 3. Does passing from 1 to 2, amounts to passing from non–efficiency to efficiency? Conjecture 10.1: NP ∪co-bfNP ⊆PMCT DC(2). (B) The role of direction in communication rules Next, we deal with complexity aspects of tissue P systems with cell divison/cell separation where only symport or antiport rules are allowed. We have: P= PMCT DA(1) =PMCT SA(1), and NP ∪co −NP ⊆PMCT DA(3) ∩PMCT SA(3). Thus, assuming P6=NP, a first frontier between efficiency and non-efficiency is obtained in the above framework when passing from communication rules with length 1 to communication rules with length at most 3. Problem 10.2. What about the complexity classes PMCT DA(2),PMCT SA(2), PMCT DS(k)and PMCT SS(k), for all k≥1? Conjecture 10.2: P =PMCT SA(2), and for all k≥1, P=PMCT SS(k). If this conjecture is true, then passing from symport rules to antiport rules with length at least three, amounts to passing from non–efficiency to efficiency, in the framework of tissue P systems with cell separation. (C) The role of the environment Classical tissue P systems have a special alphabet associated with the environment, whose elements appear at the initial configuration of the system, in an arbitrary large amount of copies. What may happen if this property is removed, that is, if we assume that the alphabet associated to the environment is empty? We use a “hat” to indicate the case when the environment is initially empty. Recently it has been proved that, for each k≥1, PMCT DC(k)= PMC[ T DC(k)[5], that is, in the framework of tissue P systems with cell division the role of the environment is not relevant from the complexity point of view. Conjecture 10.3: For each k≥1, P=PMC[ T SC(k). If this conjecture is true, then in the framework of tissue P systems with cell communication the following holds: (a) passing from separation rules to division October 10, 2013 15:33 WSPC/INSTRUCTION FILE S0129054113500202 rules (length at least three) amounts to passing from non–efficiency to efficiency; and (b) the environment provides a new borderline of efficiency. References [1] D. D´ıaz, M.A. Guti´errez, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404 (2008), 76–87. [2] R. Guti´errez-Escudero, M.J. P´erez-Jim´enez, M. Rius-Font: Characterizing tractability by tissue-like P systems. Membrane Computing. 10th International Workshop, WMC 2009, Curtea de Arge¸s, August 2009. Revised Selected and Invited Papers, LNCS 5957, Springer, Berlin, 2010, 289–300. [3] L. Pan, M.J. P´erez-Jim´enez: Computational complexity of tissue–like P systems. Journal of Complexity, 26 (2010), 296–315. [4] Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Tissue P systems with cell division. International Journal of Computers, Communications and Control, 3 (2008), 295–303. [5] M.J. P´erez-Jim´enez: The role of the environment in tissue P systems with cell division. Submitted, 2012. [6] M.J.P´erez-Jim´enez, P. Sos´ık: Improving the efficiency of tissue P systems with cell separation. Submitted, 2012.