The P versus NP problem: Unconventional insights from Membrane Computing
Abstract
: The P ?=NP question is one of the outstanding open problems in theoretical computer science. The relevance of this question is not only the inherent pleasure of solving a mathematical problem, since an answer to it would provide information of high economical interest. On the one hand, a negative answer to this question would confirm that the majority of current cryptographic systems are secure from a practical point of view. On the other hand, a positive answer would not only show the uncertainty about the secureness of these systems, but also this kind of answer is expected to come together with a general procedure such that it will provide a deterministic algorithm solving any NP-complete problem in polynomial time. In this talk, new approaches/tools to attack the previous problem are given by using Membrane Computing, a branch of Natural Computing aiming to abstract computing models from the structure and functioning of the living cell as well as from the organization of cells in tissues, organs, and other higher order structures. The devices of this paradigm constitute models for distributed, parallel and non-deterministic computing. Specifically, different borderlines between efficiency and non-efficiency are shown in terms of syntactical ingredients of cell-like and tissue like membrane systems. Each of them provide appealing characterizations of the P̸=NP conjecture within the framework of this bioinspired and unconventional computing model.
Full text
The P versus NP problem: Unconventional insights from Membrane Computing Mario J. P´erez Jim´enez Academia Europaea (The Academy of Europe) Research Group on Natural Computing Dpt. of Computer Science and Artificial Intelligence University of Sevilla, Spain www.cs.us.es/~ marper [email protected] Asian Conference on Membrane Computing November 4-7, 2013. Chengdu, China
The P versus NP problem (I) IFinding solutions versus checking the correctness of solutions. IProofs versus verifying their correctness. •This is essentially the central problem of Computational Complexity theory 2 / 32
The P versus NP problem (I) IFinding solutions versus checking the correctness of solutions. IProofs versus verifying their correctness. •This is essentially the central problem of Computational Complexity theory 2 / 32
The P versus NP problem (I) IFinding solutions versus checking the correctness of solutions. IProofs versus verifying their correctness. •This is essentially the central problem of Computational Complexity theory 2 / 32
The P versus NP problem (I) IFinding solutions versus checking the correctness of solutions. IProofs versus verifying their correctness. •This is essentially the central problem of Computational Complexity theory 2 / 32
The P versus NP problem (II) It is widely believed that it is harder Ito solve a problem than to check the correctness of a solution It is widely believed that P6=NP. 3 / 32
The P versus NP problem (II) It is widely believed that it is harder Ito solve a problem than to check the correctness of a solution It is widely believed that P6=NP. 3 / 32
The P versus NP problem (II) It is widely believed that it is harder Ito solve a problem than to check the correctness of a solution It is widely believed that P6=NP. 3 / 32
The P versus NP problem (II) It is widely believed that it is harder Ito solve a problem than to check the correctness of a solution It is widely believed that P6=NP. 3 / 32
Unconventional framework: Membrane Computing •Branch of Natural Computing initiated by Gh. P˘aun (1998-2000). IIt was selected by the Institute for Scientific Information, USA, as a Fast Emerging Research Front in Computer Science (2003). IThe devices of this paradigm (P systems or membrane systems), provide distributed parallel and nondeterministic computing models. •Acomputational complexity theory in Membrane Computing is proposed. IPolynomial complexity classes associated with (cell–like and tissue–like) P systems are presented. IA notion of acceptance must be defined in the new framework (different than the classical one for nondeterministic Turing machines) 6 / 32
Unconventional framework: Membrane Computing •Branch of Natural Computing initiated by Gh. P˘aun (1998-2000). IIt was selected by the Institute for Scientific Information, USA, as a Fast Emerging Research Front in Computer Science (2003). IThe devices of this paradigm (P systems or membrane systems), provide distributed parallel and nondeterministic computing models. •Acomputational complexity theory in Membrane Computing is proposed. IPolynomial complexity classes associated with (cell–like and tissue–like) P systems are presented. IA notion of acceptance must be defined in the new framework (different than the classical one for nondeterministic Turing machines) 6 / 32
The notion of acceptance Nondeterministic Turing machines Membrane systems Yes Yes w No No Yes Yes Yes Yes Yes w ∞ 7 / 32
Recognizer devices IUsually, complexity theory deals with decision problems which are problems that require a “yes” or “no” answer. IIn the real-life, many abstract problems are combinatorial optimization problems not decision problems. IEvery decision problem has associated a language in a natural way. IThe solvability of decision problems is defined through the recognition of the languages associated with them. 8 / 32
Recognizer devices IUsually, complexity theory deals with decision problems which are problems that require a “yes” or “no” answer. IIn the real-life, many abstract problems are combinatorial optimization problems not decision problems. IEvery decision problem has associated a language in a natural way. IThe solvability of decision problems is defined through the recognition of the languages associated with them. 8 / 32
Recognizer devices IUsually, complexity theory deals with decision problems which are problems that require a “yes” or “no” answer. IIn the real-life, many abstract problems are combinatorial optimization problems not decision problems. IEvery decision problem has associated a language in a natural way. IThe solvability of decision problems is defined through the recognition of the languages associated with them. 8 / 32
Recognizer devices IUsually, complexity theory deals with decision problems which are problems that require a “yes” or “no” answer. IIn the real-life, many abstract problems are combinatorial optimization problems not decision problems. IEvery decision problem has associated a language in a natural way. IThe solvability of decision problems is defined through the recognition of the languages associated with them. 8 / 32
Recognizer Membrane Systems •Cell-like P systems: Π = (Γ,Σ,H,µ,M1,...,Mq,R,iin,iout ) •Tissue-like P systems: Π = (Γ,Σ,E,M1,...,Mq,R,iin,iout ) IThe working alphabet contains two distinguished elements yes and no. IAll computations halt. IFor any computation of the system, either object yes or object no (but not both) must have been sent to the output region of the system, and only at the last step of the computation. •Accepting/rejecting computations for recognizer P systems 9 / 32
Recognizer Membrane Systems •Cell-like P systems: Π = (Γ,Σ,H,µ,M1,...,Mq,R,iin,iout ) •Tissue-like P systems: Π = (Γ,Σ,E,M1,...,Mq,R,iin,iout ) IThe working alphabet contains two distinguished elements yes and no. IAll computations halt. IFor any computation of the system, either object yes or object no (but not both) must have been sent to the output region of the system, and only at the last step of the computation. •Accepting/rejecting computations for recognizer P systems 9 / 32
Recognizer Membrane Systems •Cell-like P systems: Π = (Γ,Σ,H,µ,M1,...,Mq,R,iin,iout ) •Tissue-like P systems: Π = (Γ,Σ,E,M1,...,Mq,R,iin,iout ) IThe working alphabet contains two distinguished elements yes and no. IAll computations halt. IFor any computation of the system, either object yes or object no (but not both) must have been sent to the output region of the system, and only at the last step of the computation. •Accepting/rejecting computations for recognizer P systems 9 / 32
Polynomial time solvability IA decision problem Xis solvable in polynomial time by a family of recognizer membrane systems Π={Π(n) : n∈N}, iff: ?The family Πis polynomially uniform by Turing machines, that is, there exists a DTM working in polynomial time which constructs the system Π(n) from n∈N. ?There exists a pair (cod,s) of polynomial-time computable functions over IXsuch that: (a) for each instance u∈IX,s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)); (b) for each n∈N,s−1(n) is a finite set; (c) the family Πis polynomially bounded with regard to (X,cod,s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u) is halting and it performs at most p(|u|) steps; (d) the family Πis sound with regard to (X,cod,s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u) = 1; (e) the family Πis complete with regard to (X,cod,s), that is, for each u∈IX, if θX(u) = 1, then every computation of Π(s(u)) with input cod(u) is an accepting one. IWe denote it by X∈PMCR IPMCRis closed under complement and polynomial–time reductions. 11 / 32
Polynomial time solvability IA decision problem Xis solvable in polynomial time by a family of recognizer membrane systems Π={Π(n) : n∈N}, iff: ?The family Πis polynomially uniform by Turing machines, that is, there exists a DTM working in polynomial time which constructs the system Π(n) from n∈N. ?There exists a pair (cod,s) of polynomial-time computable functions over IXsuch that: (a) for each instance u∈IX,s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)); (b) for each n∈N,s−1(n) is a finite set; (c) the family Πis polynomially bounded with regard to (X,cod,s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u) is halting and it performs at most p(|u|) steps; (d) the family Πis sound with regard to (X,cod,s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u) = 1; (e) the family Πis complete with regard to (X,cod,s), that is, for each u∈IX, if θX(u) = 1, then every computation of Π(s(u)) with input cod(u) is an accepting one. IWe denote it by X∈PMCR IPMCRis closed under complement and polynomial–time reductions. 11 / 32
Polynomial time solvability IA decision problem Xis solvable in polynomial time by a family of recognizer membrane systems Π={Π(n) : n∈N}, iff: ?The family Πis polynomially uniform by Turing machines, that is, there exists a DTM working in polynomial time which constructs the system Π(n) from n∈N. ?There exists a pair (cod,s) of polynomial-time computable functions over IXsuch that: (a) for each instance u∈IX,s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)); (b) for each n∈N,s−1(n) is a finite set; (c) the family Πis polynomially bounded with regard to (X,cod,s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u) is halting and it performs at most p(|u|) steps; (d) the family Πis sound with regard to (X,cod,s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u) = 1; (e) the family Πis complete with regard to (X,cod,s), that is, for each u∈IX, if θX(u) = 1, then every computation of Π(s(u)) with input cod(u) is an accepting one. IWe denote it by X∈PMCR IPMCRis closed under complement and polynomial–time reductions. 11 / 32
Solvability of a decision problem u I X ∋ ? input AnswerAnswer of theof the polynomial encoding problem P system Π cod s cod(u) (s(u)) 12 / 32
Efficiency of a membrane system IEfficiency: Capability to solve NP-complete problems in polynomial time. INP ∪co-NP ⊆PMCR. INon-Efficiency:P=PMCR. Frontiers of the efficiency: IM1efficient. IM2non efficient. IM2⊆M1: each solution Sof a problem Xin M2is also a solution in M1. Passing from M2to M1amounts to passing from non efficiency to efficiency. 13 / 32
Efficiency of a membrane system IEfficiency: Capability to solve NP-complete problems in polynomial time. INP ∪co-NP ⊆PMCR. INon-Efficiency:P=PMCR. Frontiers of the efficiency: IM1efficient. IM2non efficient. IM2⊆M1: each solution Sof a problem Xin M2is also a solution in M1. Passing from M2to M1amounts to passing from non efficiency to efficiency. 13 / 32
Efficiency of a membrane system IEfficiency: Capability to solve NP-complete problems in polynomial time. INP ∪co-NP ⊆PMCR. INon-Efficiency:P=PMCR. Frontiers of the efficiency: IM1efficient. IM2non efficient. IM2⊆M1: each solution Sof a problem Xin M2is also a solution in M1. Passing from M2to M1amounts to passing from non efficiency to efficiency. 13 / 32
Efficiency of a membrane system IEfficiency: Capability to solve NP-complete problems in polynomial time. INP ∪co-NP ⊆PMCR. INon-Efficiency:P=PMCR. Frontiers of the efficiency: IM1efficient. IM2non efficient. IM2⊆M1: each solution Sof a problem Xin M2is also a solution in M1. Passing from M2to M1amounts to passing from non efficiency to efficiency. 13 / 32
Managing frontiers of the efficiency Non efficiency Efficiency MM 2 1 14 / 32
Attacking the P versus NP problem Non efficiency Efficiency MM 2 1 P=NP IFinding an NP-complete problem efficiently solvable in M2. ITraslating a polynomial time solution of an NP-complete problem in M1, to a a polynomial time solution in M2. P6=NP IFinding an NP-complete problem that is not polynomial time solvable in M2. 15 / 32
Efficiency of P systems with active membranes •Proposition 3: A deterministic P system with active membranes but without membrane division can be simulated by a DTM with a polynomial slowdown. Theorem: P =PMCNAM. •Efficient solutions to NP–complete problems in AM(−ne): INP ∪co-NP ⊆PMCAM(−ne)(Sevilla team 2003, A. Alhazov, C. Mart´ın and L. Pan, 2004). •Aborderline between efficiency and non–efficiency: division rules in the framework of AM(−ne). •Bounds for the complexity class PMCAM(+ne): IPSPACE ⊆PMCAM(+ne)⊆EXP (A.E. Porreca, G. Mauri and C. Zandron, 2006). •Conclusion: AM is too powerful from the complexity point of view. 19 / 32
Efficiency of P systems with active membranes •Proposition 3: A deterministic P system with active membranes but without membrane division can be simulated by a DTM with a polynomial slowdown. Theorem: P =PMCNAM. •Efficient solutions to NP–complete problems in AM(−ne): INP ∪co-NP ⊆PMCAM(−ne)(Sevilla team 2003, A. Alhazov, C. Mart´ın and L. Pan, 2004). •Aborderline between efficiency and non–efficiency: division rules in the framework of AM(−ne). •Bounds for the complexity class PMCAM(+ne): IPSPACE ⊆PMCAM(+ne)⊆EXP (A.E. Porreca, G. Mauri and C. Zandron, 2006). •Conclusion: AM is too powerful from the complexity point of view. 19 / 32
Efficiency of P systems with active membranes •Proposition 3: A deterministic P system with active membranes but without membrane division can be simulated by a DTM with a polynomial slowdown. Theorem: P =PMCNAM. •Efficient solutions to NP–complete problems in AM(−ne): INP ∪co-NP ⊆PMCAM(−ne)(Sevilla team 2003, A. Alhazov, C. Mart´ın and L. Pan, 2004). •Aborderline between efficiency and non–efficiency: division rules in the framework of AM(−ne). •Bounds for the complexity class PMCAM(+ne): IPSPACE ⊆PMCAM(+ne)⊆EXP (A.E. Porreca, G. Mauri and C. Zandron, 2006). •Conclusion: AM is too powerful from the complexity point of view. 19 / 32
Efficiency of P systems with active membranes •Proposition 3: A deterministic P system with active membranes but without membrane division can be simulated by a DTM with a polynomial slowdown. Theorem: P =PMCNAM. •Efficient solutions to NP–complete problems in AM(−ne): INP ∪co-NP ⊆PMCAM(−ne)(Sevilla team 2003, A. Alhazov, C. Mart´ın and L. Pan, 2004). •Aborderline between efficiency and non–efficiency: division rules in the framework of AM(−ne). •Bounds for the complexity class PMCAM(+ne): IPSPACE ⊆PMCAM(+ne)⊆EXP (A.E. Porreca, G. Mauri and C. Zandron, 2006). •Conclusion: AM is too powerful from the complexity point of view. 19 / 32
Efficiency of P systems with active membranes •Proposition 3: A deterministic P system with active membranes but without membrane division can be simulated by a DTM with a polynomial slowdown. Theorem: P =PMCNAM. •Efficient solutions to NP–complete problems in AM(−ne): INP ∪co-NP ⊆PMCAM(−ne)(Sevilla team 2003, A. Alhazov, C. Mart´ın and L. Pan, 2004). •Aborderline between efficiency and non–efficiency: division rules in the framework of AM(−ne). •Bounds for the complexity class PMCAM(+ne): IPSPACE ⊆PMCAM(+ne)⊆EXP (A.E. Porreca, G. Mauri and C. Zandron, 2006). •Conclusion: AM is too powerful from the complexity point of view. 19 / 32
Polarizationless P systems with active membranes •Π = (Γ,Σ,H, µ, M1,...,Mq,R,iin,iout ) : (a)[a→u]h(object evolution rules). (b)a[ ]h→[b]h(send–in communication rules). (c)[a]h→[ ]hb(send–out communication rules). (d)[a]h→b(dissolution rules). (e)[a]h→[b]h[c]h(division rules for elementary membranes). (f)[ [ ]h1[ ]h2]h→[ [ ]h1]h[ [ ]h2]h(division rules for non–elementary membranes). •The sets NAM0,AM0(α, β),where α∈ {−d,+d}and β∈ {−ne,+ne}. 20 / 32
A P˘aun’s conjecture At the beginning of 2005, Gh. P˘aun (problem Ffrom 1) wrote: My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible – and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non–efficiency to efficiency. The so–called P˘aun’s conjecture can be formally formulated: P=PMCAM0(+d,−ne) 1Gh. P˘aun: Further twenty six open problems in membrane computing. Third Brainstorming Week on Membrane Computing (M.A. Guti´errez et al. eds.), F´enix Editora, Sevilla, 2005, pp. 249–262. 21 / 32
Partial answers AFFIRMATIVE •Non efficiency of AM0(−d,+ne) Theorem: P =PMCAM0(−d,+ne)(Sevilla team, 2006). IThe notion of dependency graph. NEGATIVE •Efficiency of AM0(+d,+ne): IPSPACE ⊆PMCAM0(+d,+ne)(A. Alhazov, P-J, 2007). A borderline of the efficiency Idissolution rules in AM0(+ne). 22 / 32
Partial answers AFFIRMATIVE •Non efficiency of AM0(−d,+ne) Theorem: P =PMCAM0(−d,+ne)(Sevilla team, 2006). IThe notion of dependency graph. NEGATIVE •Efficiency of AM0(+d,+ne): IPSPACE ⊆PMCAM0(+d,+ne)(A. Alhazov, P-J, 2007). A borderline of the efficiency Idissolution rules in AM0(+ne). 22 / 32
Partial answers AFFIRMATIVE •Non efficiency of AM0(−d,+ne) Theorem: P =PMCAM0(−d,+ne)(Sevilla team, 2006). IThe notion of dependency graph. NEGATIVE •Efficiency of AM0(+d,+ne): IPSPACE ⊆PMCAM0(+d,+ne)(A. Alhazov, P-J, 2007). A borderline of the efficiency Idissolution rules in AM0(+ne). 22 / 32
Tissue-like membrane systems (II) •Tissue P systems with cell division: ISymport-antiport rules. I[a]i→[b]i[c]i, where i∈ {1,2,...,q}and a,b,c∈Γ (division rules). •Tissue P systems with cell separation: ISymport-antiport rules. I[a]i→[ Γ1]i[ Γ2]i, where i∈ {1,2,...,q},a∈Γ, i6=iout and {Γ1,Γ2}is a fixed partition of Γ (separation rules). •The sets T DC,T SC, and T DC(k),T SC(k), for each k≥1. 25 / 32
•Cell Division. •Cell Separation. 26 / 32
•Cell Division. •Cell Separation. 26 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems •P=PMCT C (Sevilla team, 2009). •P=PMCT DC(1) (Sevilla team, 2010). •P=PMCT SC(2) (L. Pan, P-J, A. Riscos, M. Rius, 2012). •NP ∪co −NP ⊆PMCT DC(2) (A. Porreca, N. Murphy, P-J, 2012). •NP ∪co −NP ⊆PMCT SC(3) (P. Sos´ık, P-J, 2012). Borderlines of the efficiency Idivision rules in the framework of T C. Ilength of communication rules in the framework of T D:passing from 1 to 2 amounts to passing from non–efficiency to efficiency. Ilength of communication rules in the framework of T S:passing from 2 to 3 amounts to passing from non–efficiency to efficiency. 27 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Efficiency of tissue P systems without environment Division rules •For each k:PMC\ T DC(k+1) =PMCT DC(k+1) (Sevilla team, 2012). IP=PMC\ T DC(1). INP ∪co −NP ⊆PMC\ T DC(2). •The length of communication rules provides a new borderline of the efficiency in the framework d T D. Separation rules •P=PMC[ T SC (Sevilla team, 2013). IP=PMC[ T SC(3). INP ∪co −NP ⊆PMCT SC(3). Borderlines of the efficiency IThe environment in the framework T SC(3). 30 / 32
Conclusions: New Frontiers of the efficiency IKind of the rules: IDivision rules in AM. IDivision rules in T C. IDissolution rules in AM0(+ne). IThe length of communication rules: IPassing from 1 to 2 in T D. IPassing from 1 to 2 in d T D. IPassing from 2 to 3 in T S. IThe environment: IIn the framework T SC(3). Each of them provides a new way to attack the P versus NP problem. 31 / 32