P systems with evolutional communication and division rules

axioms Article P Systems with Evolutional Communication and Division Rules David Orellana-Martín 1,* , Luis Valencia-Cabrera 1,2 and Mario J. Pérez-Jiménez 1,2   Citation: Orellana-Martín, D.; Valencia-Cabrera, L.; Pérez-Jiménez, M.J. P Systems with Evolutional Communication and Division Rules. Axioms 2021,10, 327. https:// doi.org/10.3390/axioms10040327 Academic Editors: Cristian S. Calude and Gheorghe P˘aun Received: 1 October 2021 Accepted: 24 November 2021 Published: 30 November 2021 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). 1Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain; [email protected] (L.V.-C.); [email protected] (M.J.P.-J.) 2Smart Computer Systems Research and Engineering Lab (SCORE), Research Institute of Computer Engineering (I3US), Universidad de Sevilla, 41012 Sevilla, Spain *Correspondence: dor[email protected] Abstract: A widely studied field in the framework of membrane computing is computational complexity theory. While some types of P systems are only capable of efficiently solving problems from the class P , adding one or more syntactic or semantic ingredients to these membrane systems can give them the ability to efficiently solve presumably intractable problems. These ingredients are called to form a frontier of efficiency, in the sense that passing from the first type of P systems to the second type leads to passing from non-efficiency to the presumed efficiency. In this work, a solution to the SAT problem, a well-known NP -complete problem, is obtained by means of a family of recognizer P systems with evolutional symport/antiport rules of length at most (2,1) and division rules where the environment plays a passive role; that is, P systems from \ CDEC( 2,1 ) . This result is comparable to the one obtained in the tissue-like counterpart, and gives a glance of a parallelism and the non-evolutionary membrane systems with symport/antiport rules. Keywords: membrane computing; computational complexity theory; P vs. NP problem; evolutional communication; symport/antiport MSC: 68Q07; 68Q15 1. Introduction Membrane computing is a bio-inspired paradigm of computation, based on the structure and behavior of living cells. Introduced in 1998 by Gh. P˘aun [ 1 ], giving birth to devices known as membrane systems or P systems. There are several different types of P systems, but three of them are specially studied: cell-like membrane systems [ 1 ], whose tree-like structure characterizes the relation between its regions; tissue-like membrane systems [2], defined as a set of cells that can interact between them and with the environment, and neural-like membrane systems [ 3 ], having an explicitly defined directed graph as a relation of the neurons through synapses. The last paradigm is being intensely studied in practical applications, and different variants have been created to their use in different fields [ 4 – 6 ] The paradigm of membrane computing is very wide, covering topics from theory [ 7 , 8 ] to applications [9–11], dedicating a branch to simulators and in silico implementations [12]. A widely studied question in this framework from the very beginning is which kind of problems can be solved by means of membrane systems. Membrane systems can differ in the type of objects with which they can compute (e.g., symbols, strings, matrices), the type of relation between the regions (e.g., hierarchical structure, directly connected membranes, cells implicitly connected by the rules) and the rules governing the computation of the system (e.g., object evolution rules, symport/antiport rules, division rules), among others. This variety of ingredients can change not only the type of problem that a P system can solve, but how efficiently can it solve a certain problem. More precisely, decision problems are usually studied in the field of computational complexity theory Axioms 2021,10, 327. https://doi.org/10.3390/axioms10040327 https://www.mdpi.com/journal/axioms Axioms 2021,10, 327 2 of 12 in order to classify them in complexity classes that contain problems that can be solved with a similar amount of computational resources [13]. Recognizer membrane systems [ 14 ] are P systems with certain ingredients, such as two special objects yes and no , and requisites, such as all the computations halt and return the same result. The design of a family of recognizer membrane systems of a certain type R solving certain decision problems can reveal which kind of problems can be solved efficiently by means of that class of P systems. A widely studied type of membrane systems in the field of computational complexity theory is the framework of tissue P systems with symport/antiport rules. In [ 15 ], a polynomial-time solution to SAT was designed by means of a family of recognizer tissue P systems with symport/antiport rules of length at most five and division rules. In this type of P system, the length is defined as the number of objects implied in the symport/antiport rules of the system (e.g., the length of the rule (i , u/v , j) is |u|+|v| ). This result was eventually improved in [ 16 ], where the maximum number of objects implied in a communication rule was two. If only one object was allowed in communication rules, then only tractable problems could be efficiently solved, as demonstrated in [ 17 ]. A similar frontier of efficiency was found by using separation rules instead of division rules in [ 18 , 19 ], but in this case, the frontier is from passing of communication rules of length at most two to length at most three, instead of passing from one to two. Some results about their relative environmentless counterparts were demonstrated in [ 20 , 21 ]. Symport/antiport rules were first introduced in tissue-like membrane systems, but later used in cell-like membrane systems, where results were surprisingly similar [ 22 – 27 ], giving a glance of the similarity of using both tree-like and directed graph structures. In [ 28 ], tissue P systems with evolutional symport/antiport rules were introduced, including in communication rules the capability to evolve the objects while traveling from one region to another one. In this type of P system, two different definitions of length can be cited: On the one hand, the length of an evolutional communication rule can be defined with a single number that is related with the number of objects in the whole rule (e.g., in the rule hu[v]jii→hv0[u0]jii is |u|+|v|+|u0|+|v0| ); on the other hand, the length can be defined as a pair of numbers concerning the number of objects in the left-hand side and the right-hand side of the evolutional communication rules of the system (e.g., the length of the rule hu[v]jii→hv0[u0]jii is (|u|+|v| , |u0|+|v0|) ). In [ 29 ], several new results were presented, publishing some improvements from [ 28 , 30 – 32 ]. More precisely, in [ 32 ] an efficient family of tissue P systems with evolutional communication rules of length at most ( 2,1 ) and division rules using the environment as an active agent of the system solving the SAT problem is presented. In this work, we investigate the role of evolutional communication rules in cell-like membrane systems that use division rules as exponential workspace-generating rules, and letting the environment as a mere agent that only receives the corresponding answer of the system. The rest of the paper is structured as follows: Section 2is dedicated to introducing some terms used throughout the work. In the next section, cell P systems with evolutional symport/antiport rules and division rules are defined, and their recognizer versions are introduced. Sections 4and 5are devoted to present a solution to the problem SAT by means of a family of P systems with evolutional communication rules and division rules of length at most ( 2,1 ) , and to prove the correctness of the solution. Finally, in Section 6the results of this paper are discussed, and comparatives with other classes of P systems are given, and some open research lines are proposed, besides a description of the work in progress. 2. Preliminaries In this section, some concepts that will be used throughout the paper will be defined. The reader can find expanded and deeper information about formal languages and membrane computing in [8,33]. An alphabet is a non-empty (finite) set, whose elements are usually called symbols. A string over Γis a ordered finite succession of elements from Γ. We denote the empty string by λ. Axioms 2021,10, 327 3 of 12 Given two sets A and B , the relative complement A\B is defined as A\B={x∈A| x6∈ B}. For each set A, we denote by |A|the cardinal (number of elements) from A. A multiset can be described explicitly as follows: {(a1 , M(a1)) , . . . , (an , M(an))} , and the notation M=aM(a1) 1. . . aM(an) n will be used. The cardinal of a multiset M over Γ={a1 , . . . , an} is defined as |M| =M(a1) + . . . +M(an) . We denote by Mf(Γ) the set of all the finite multisets over Γ, and M+ f(Γ) = Mf(Γ)\ {∅} Given two multisets M1 and M2 over Γ , the union of the multisets, denoted as M1∪M2 or M1+M2 , is the application over Γ defined as: for each a∈Γ , (M1∪M2)(a) = M1(a) + M2(a) . A multiset M1 is included in M2 , and it is denoted by M1⊆M2 , if M1(a)≤M2(a) for each a∈Γ. 3. P Systems with Evolutional Communication and Division Rules In this section, the framework of cell-like membrane systems where evolutional communication rules and division rules are used is introduced. Definition 1. A P system with evolutional symport/antiport rules and division rules of degree q≥1is a tuple Π=Γ,E,µ,M1, . . . , Mq,R1, . . . , Rq,iout where: •Γis a finite (working) alphabet; •E ⊆ Γis the environment alphabet; •µis a rooted tree structure; •M1, . . . , Mqare the initial multisets of the membranes; •R1, . . . , Rqare the rules of the membranes of the system of the following form: –hu[ ]jii→h[u0]jii , with 0 ≤i , j≤q , i6=j , u∈M+ f(Γ) , u0∈Mf(Γ) ; in the case that i= 0, then u must contain at least one object from Γ\ E (evolutional send-in symport rules); –h[u]jii→hu0[ ]jii , with 0 ≤i , j≤q , i6=j , u∈M+ f(Γ) , u0∈Mf(Γ) (evolutional send-out symport rules); –hu[v]jii→hv0[u0]jii , with 0 ≤i , j≤q , i6=j , u , v∈M+ f(Γ) , u0 , v0∈Mf(Γ) (evolutional antiport rules); –[a]i→[b]i[c]i , with 1 ≤i≤q , i6∈ {iout , iskin} , a , b , c∈Γ , being iskin the label of the skin membrane (division rules). •iout ∈ {0, 1, . . . , q}is the output region of the system. A P system with evolutional symport/antiport rules and division rules of degree q≥ 1 can be seen as a set of q membranes biyectively labelled by 1, . . . , q organized in the rooted tree structure µ , whose root node is the skin membrane, and such that (a) E represents the set of objects that are situated in the environment an arbitrary number of times; (b) M1 , . . . , Mq represents the initial multisets situated in the q membranes of the system; (c) iout is a distinguished region i that will encode the output of the system. The term region i will be used to denote the membrane i , in case 1 ≤i≤q , and to the environment in the case i= 0 or i=env . We will use env and 0 indistinguishably as the label of the environment. If E=∅, it is usually omitted from the tuple. Aconfiguration at an instant t of such a system is described by the membrane structure of the P system at the instant t , the multisets of objects from Γ in each membrane at that instant and the multiset of objects from Γ\ E situated in the environment. The initial configuration of Π=Γ,E,µ,M1, . . . , Mq,R1, . . . , Rq,ioutis (µ,M1, . . . , Mq,∅). Aevolutional send-in symport rule is applicable to a configuration Ct at an instant t if there exists a region labelled by i that has at least a child membrane labelled by j and that it Axioms 2021,10, 327 4 of 12 contains the multiset u of objects. The execution of such a rule hu[ ]jii→h[u0]jii in Ct consumes the objects of u from such a region i , and it produces the multiset of objects u0 in the child membrane jin Ct. Aevolutional send-out symport rule is applicable to a configuration Ct at an instant t if there exists a region labelled by i that has at least a child membrane labelled by j and the child membrane contains the multiset u of objects. The execution of such a rule h[u]jii→hu0[ ]jii in Ct consumes the objects of u from such a region j , and it produces the multiset of objects u0in the child membrane iin Ct. Aevolutional antiport rule is applicable to a configuration Ct at an instant t if there exists a region labelled by i that contains a multiset of objects u and it has at least a child membrane labelled by j and the child membrane contains the multiset v of objects. The execution of such a rule hu[v]jii→hv0[u0]jii in Ct consumes the objects of u from such a region j and objects from v from such a region i , and it produces the multiset of objects u0 in that membrane iand the multiset of objects v0in that membrane jin Ct. Adivision rule is applicable to a configuration Ct at an instant t if there exists a region labelled by i that contains an object a . The execution of such a rule [a]i→[b]i[c]i in Ct consumes the object a from the membrane i , the membrane is duplicated with its contents included, and objects band care produced one in each new membrane created in Ct. As in tissue P systems with evolutional symport/antiport rules, two definitions of length (or size) can be described. On the one hand, the length of a evolutional communication rule r≡hu[v]jii→hv0[u0]jii can be length(r)=(|u|+|v|+|u0|+|v0|) ; on the other hand, it can be described as a pair length0(r) = (|u|+|v| , |u0|+|v0|) . The first description corresponds with the sum of the cardinalities of all the multisets in the rule, while the second definition corresponds with the pair such that the first component corresponds with the sum of cardinalities of the left-hand side of the rule (LHS), and the second component corresponds with the sum of the cardinalities of the right-hand side of the rule (RHS). If ris a symport rule, then |v|=|v0|=0 or |u|=|u0|=0. We say that a configuration Ct of a P system with evolutional communication rules and division rules Π produces a configuration Ct+1 in a transition step, denoted by Ct⇒ΠCt+1 and we say that Ct+1 is a next configuration of Ct if we can pass from Ct to Ct+1 applying the rules of Πaccording to the following principles: • At most one rule can be applied to each object of each membrane (selected in a nondeterministic way). • For each membrane i , either evolutional communication rules hu[v]jii→hv0[u0]jii or a single division rule [a]i→[b]i[c]i can be applied. In the case of applying evolutional communication rules at configuration Ct , they would be selected in a non-deterministic, parallel and maximal way; that is, all the objects in the membrane i that can fire a rule, will fire it. In the case that a division rule [a]i→[b]i[c]i is applied, it will be selected in a non-deterministic way. It can be seen as the division rule blocks the communication of the membrane with its corresponding parent membrane. All the rules are applied in an atomic way, but in order to be precise, it can be that two microsteps are executed: first, all the evolutional communication rules are executed, and then division rules are executed. It is worth taking this into account since a membrane i being divided can still communicate with its inner membranes in the same transition step. A configuration Ct is a halting configuration if no rules can be applied to such configuration at an instant t. A computation C of a P system Π can be described as a tuple C= (C0 , C1 , . . .) , where each configuration Ct+1 can be obtained from Ct , except for the initial configuration C0 . We say that C is a halting computation of length n+ 1 if the configuration Cn is a halting configuration. Axioms 2021,10, 327 5 of 12 Recognizer membrane systems were introduced in [ 14 ] as a way to solve decision problems. We define here recognizer P systems with evolutional communication rules and division rules. Definition 2. A recognizer P system with evolutional communication rules and division rules of degree q ≥1is a tuple (Π,Σ,iin), where: •Π=Γ,E,µ,M1, . . . , Mq,R1, . . . , Rq,iout is a P system with evolutional communication rules and division rules of degree q , with {yes , no} ⊆ Γ\ E two distinguished objects that will represent the output of the system, and Mi⊆Γ\Σfor 1≤i≤q; •Σ⊆Γ\ E is the input alphabet; •iin ∈ {1, . . . , q}is the label of the input membrane; •iout =0; •All the computations of Πhalt. • If C is a computation of Π , then either an object yes or an object no , but not both, are sent to the environment in the last step of the computation. Let Π=Γ,Σ,E,µ,M1, . . . , Mq,R1, . . . , Rq,iin,iout be a recognizer P system of this type, then for each input multiset m over Σ , we consider the system Π with input multiset m , and we denote it by Π+m . This is characterized by the fact that the multisets associated with the initial configuration of the system is: (M1 , . . . , Miin +m , . . . , Mq , ∅) ; that is, it is obtained from the initial configuration (M1 , . . . , Miin , . . . , Mq , ∅) of Π , by adding the multiset mto Miin . We define then a Output(C) function whose domain is the set of computations of Π . Such a function will formalize the results or outputs of the system. If C is a computation of the system Π , then Output(C) = yes (respectively, Output() = no ) if the object yes (resp., object no ) appears in the environment associated to the halting configuration of C , but does not appear in any other configuration of C . A computation C will be called an accepting computation (respectively, a rejecting computation) if Output(C) = yes (resp., Output(C) = no ). Computations of recognizer membrane systems always halt, and will return either yes or no as a response. A recognizer membrane system with input multiset Π+m is confluent, in the sense that all the computations give the same answer; that is, given an input multiset m , all the computations of a recognizer membrane system with input multiset Π+mwill be either accepting computations or rejecting computations. The class of recognizer P systems with evolutional symport/antiport rules of length at most k (respectively, with length at most (k1 , k2) ) and division rules is denoted by CDEC((k)) (resp., CDEC((k1 , k2)) ). If the environment does not play an active role, we say that it is a recognizer P system with symport/antiport rules of length at most k (resp., with length at most (k1 , k2) , i.e. LHS with length at most k1 and RHS with length at most k2 ) and division rules without environment, and we denote this class of systems by \ CDEC(k) (resp., \ CDEC(k1,k2)). In this work, a family of recognizer P systems will be used in order to solve decision problems. Let X= (IX , θX) a decision problem. We say that X is solvable in polynomial time by means of a uniform family of recognizer P systems Π={Π(n):n∈N} of the class R, and we denote it by X∈PMCR, if the following conditions hold: (a) Π is polynomially uniform by Turing machines; that is, there exists a Turing machine that constructs Π(n)in polynomial time. (b) There exists a polynomial encoding (cod,s)of Xsuch that: b.1 Π is polynomially bounded with respect to (X , cod , s) ; that is, there exists k∈N such that for each u∈IX , each computation of Π(s(u)) + cod(u) runs, at most, for |u|kcomputation steps. b.2 Πis sound and complete with respect to (X,cod,s). Axioms 2021,10, 327 6 of 12 4. Methods Let ϕ a propositional formula in CNF with n variables and p clauses. Let s(ϕ) = hn , pi and cod(ϕ) contains xi,j,0 if the literal xi is in the clause Cj , xi,j,0 if the literal ¬xi is in the clause Cj and x∗ i,j,0 if the variable xi does not appear in the clause Cj . Let the function ⊥(i , j) = i⊥j=i+jn . Then, the system Π(hn , pi) will be the responsible of solving ϕ . Let Π(hn,pi) = (Γ,Σ,E,µ,M1, . . . , Mnp+5,R1, . . . , Rnp+5,iin,iout) a recognizer membrane system from CDEC((2,1)), where: 1. The working alphabet Γ=Σ∪ {yes,no,y1,y2,n1,n2,α0,#} ∪ {ai,j,Ti,j,Fi,j,xi,j,xi,j,x∗ i,j|1≤i≤n,1 ≤j≤p} ∪ {xi,j,k,xi,j,k,x∗ i,j,k|1≤i≤n,1 ≤j≤p,1 ≤k≤np +bnp/2c+1} ∪ {cj|1≤j≤p}∪{αj|1≤j≤p+1} ∪ {γk|0≤k≤np +2} ∪ {δk|0≤k≤np +3}∪{δ0 k|0≤k≤np +1}. 2. The input alphabet Σ={xi,j,0,xi,j,0,x∗ i,j,0 |1≤i≤n,1 ≤j≤p}. 3. Environment alphabet E=∅. 4. µ= [ [ ]1[ ]2. . . [ ]np[ ]np+2[ ]np+3[ ]np+4[ ]np+5]np+1 5. Mk=∅,1 ≤k≤np +1, Mnp+2={ai,j|1≤i≤n,1 ≤j≤p} ∪ {αj|1≤j≤p+1}, Mnp+3={δ0 0},Mnp+4={δ0},Mnp+5={γ0}. 6. The set of rules R=R1∪. . . Rnp+5contains the following rules: 6.1 Rules for generating all the necessary γnp+2to simulate the environment. [γk]np+5→[γk+1]np+5[γk+1]np+5for 0≤k≤np +1 h[γnp+2]np+5inp+1→hγnp+2[ ]np+5inp+1 6.2 Rules to generate p copies of the 2 n possible truth assignments. For that, 2 np “partial” truth assignments will be generated. ai,jnp+2→[Ti,j]np+2[Fi,j]np+2 h[Ti,jFi,j0]np+2inp+1→h#[ ]np+2inp+1    for 1≤i≤n 1≤j,j0,≤p 6.3 Rules to generate 2np copies of cod(ϕ). hxi,j,0 [ ]i⊥jinp+1→h[xi,j,1 ]i⊥jinp+1 hxi,j,0 [ ]i⊥jinp+1→h[xi,j,1 ]i⊥jinp+1 hx∗ i,j,0 [ ]i⊥jinp+1→h[x∗ i,j,1 ]i⊥jinp+1            for 1≤i≤n,1 ≤j≤p hxi,j,kii⊥j→[xi,j,k+1]i⊥j[xi,j,k+1]i⊥j hxi,j,kii⊥j→[xi,j,k+1]i⊥j[xi,j,k+1]i⊥j hx∗ i,j,kii⊥j→[x∗ i,j,k+1]i⊥j[x∗ i,j,k+1]i⊥j            for 1≤i≤n 1≤j≤p 1≤k≤np +bnp/2c h[xi,j,np+bnp/2c+1]i⊥jinp+1→hxi,j[ ]i⊥jinp+1 h[xi,j,np+bnp/2c+1]i⊥jinp+1→hxi,j[ ]i⊥jinp+1 h[x∗ i,j,np+bnp/2c+1]i⊥jinp+1→hx∗ i,j[ ]i⊥jinp+1            for 1≤i≤n,1 ≤j≤p hγnp+2[δ0 0]np+3inp+1→h[δ0 1]np+3inp+1 δ0 knp+3→[δ0 k+1]np+3[δ0 k+1]np+3for 1 ≤k≤np h[δ0 np+1]np+3inp+1→hδ0 np+1[ ]np+3inp+1 6.4 Rules to check which clauses are satisfied. Axioms 2021,10, 327 7 of 12 hxi,j[Ti,j]np+2inp+1→h[cj]np+2inp+1 hxi,j[Ti,j]np+2inp+1→h[#]np+2inp+1 hx∗ i,j[Ti,j]np+2inp+1→h[#]np+2inp+1 hxi,j[Fi,j]np+2inp+1→h[#]np+2inp+1 hxi,j[Fi,j]np+2inp+1→h[cj]np+2inp+1 hx∗ i,j[Fi,j]np+2inp+1→h[#]np+2inp+1                                for 1≤i≤n,1 ≤j≤p 6.5 Rules to check if all the clauses are satisfied by a truth assignment. hδ0 np+1[αp+1]np+2inp+1→h[α0]np+2inp+1 h[cjαj]np+2inp+1→h#[ ]np+2inp+1for 1≤j≤p h[αjα0]np+2inp+1→hn1[ ]np+2inp+1for 1≤j≤p 6.6 General counter. hγnp+2[δk]np+5inp+1→h[δk+1]np+5inp+1for 0≤k≤np +2 h[δnp+3]np+5inp+1→hδnp+3[ ]np+5inp+1 6.7 Rules to return a negative answer. hn1[ ]np+2inp+1→h[n1]np+2inp+1 hδnp+3[n1]np+2inp+1→hn2[ ]np+2inp+1 h[n2]np+1i0→hno [ ]np+1i0 6.8 Rules to return an affirmative answer. hδnp+3[α0]np+2inp+1→h[y1]np+2inp+1 h[y1]np+2inp+1→hy2[ ]np+2inp+1 h[y2]np+1i0→hyes [ ]np+1i0 6.9 Input membrane iin =np +1 and output membrane iout =0. In this section, the behaviour of a recognizer P system from CDEC((2,1)) solving an instance ϕ from SAT is described. Let ϕ=C1∧. . . ∧Cp be a propositional logic formula in CNF, where Cj=l1∨. . . ∨lrj , lk∈ {xi , ¬xi| 1 ≤i≤n} . Then ϕ will be processed by the system Π(s(ϕ)) + cod(ϕ) , where s(ϕ) = hn , pi and cod(ϕ) = {xi,j,0 |xi∈Cj}∪{xi,j,0 | ¬xi∈Cj} ∪ {x∗ i,j,0 |xi6∈ Cj∧ ¬xi6∈ Cj}. Let us note codk(ϕ) the set of all the elements from cod(ϕ) with the third subscript equal to k. Let us note cod∗(ϕ)the set of all the elements from cod(ϕ)without the third subscript. The solution follows a brute force algorithm protocol in the framework of recognizer P systems with evolutional symport/antiport rules and division rules, and consists of the following stages: 4.1. Generation Stage In the generation stage, different elements necessary for the rest of the computation are generated at the same time. First, in order to avoid the use of the environment to obtain γ objects, it is necessary to use some of the synchronization protocols in [ 32 ], 2 np+2 copies of the object γnp+2 will be generated in membranes np + 5 through the rules from 6.1. These objects will be present in the membrane np + 1 at configuration Cnp+3 . For generating the different truth assignments, objects Ti,j and Fi,j will represent a partial truth assignment of the variable xi in the following sense: Objects Ti,j and Fi,j0 , with i6=j , would be incompatible, since two different values would be assigned to the same variable. Therefore, in order to remove this possibility, these two objects will be removed from the system by Axioms 2021,10, 327 8 of 12 means of the rule h[Ti,jFi,j0]np+2inp+1→h#[ ]np+2inp+1 . After applying these rules, only “real” truth assignments would be present in the system. In fact, there can be assignments where a variables has not been assigned any value. In this case, it will not return a false positive. For generating the different np partial truth assignments, np computational steps should be applied, but since rules are fired in a non-deterministic way, and the removal of these incompatible variables could be applied in between the process of generation, at most bnp/ 2 c extra steps should be taken into account. Therefore, in configuration Cnp+bnp/2c , membranes labelled by np +2 will contain all the possible truth assignments. Besides, objects from cod(ϕ) will be sent into their corresponding membrane. From the second computational step, membranes 1, . . . , np will be duplicated in each step until having 2 np+bnp/2c copies of the corresponding object from codnp+bnp/2c(ϕ) . These objects will be sent out to the membrane np + 1, and therefore in the configuration Cnp+bnp/2c+1 , 2 np+bnp/2c copies of cod∗(ϕ) will be present in the membrane np + 1. In this configuration, the next stage begins. 4.2. First Checking Stage In this stage, objects from cod∗(ϕ) will react with objects Ti,j and Fi,j through rules from 6.4. In this stage, an object cj will be generated in a membrane np + 2 if and only if the truth assignment represented in that membrane makes true the corresponding literal. This stage takes one computational step. At the same time, counters δk and δ0 k are being generated. δk will evolve by using objects γnp+2 as “catalysts”, and np copies of the object δ0 np+1 will be present at the membrane np + 1 at configuration C2np+5 . When this happens, the second checking stage starts. 4.3. Second Checking Stage The ( 2 np + 6 ) -thstepwillconsistoftheapplicationoftherule hδ0 np+1[αp+1]np+2inp+1→ h[α0]np+2inp+1 , creating an object α0 in each membrane labelled by np + 2. At the same time, objects cj present in a membrane will remove the corresponding object aj ; that is, the absence of an object aj in a membrane np + 2 represents that clause Cj is satisfied by the corresponding truth assignment. The object α0 will fire a rule h[αjα0]np+2inp+1→hn1[ ]np+2inp+1 if there exists an object ajin such a membrane. This stage takes exactly two computational steps. 4.4. Output Stage In configuration C2np+7 , the existence of an object α0 in a membrane labelled by np + 2 implies that no objects αj remained in such a membrane; that is, that all clauses are satisfied by the corresponding truth assignment. Therefore, if there exists an object α0 in such a membrane, it implies that the formula ϕ is satisfiable. Thus, two different scenarios can be observed. On the one hand, if the formula is satisfiable, there exists at least one membrane labelled by np + 2 at configuration C2np+7 such that it contains an object α0 . In the next step, an object y1 will be generated in such a membrane, that will be sent out, first to membrane np + 1 as an object y2 , and finally to the environment as an object yes . On the other hand, if the formula is unsatisfiable, no objects α0 remain in any of the membranes labelled by np + 2 at configuration C2np+7 . Objects n1 will be sent to the membrane np + 1 and, in the next step, they will be sent back to any membrane np + 2, taking into account that the target membranes are selected in a non-deterministic way. In the next step, as the object δnp+3 still exists in membrane np + 1, it reacts with an object n1 , transforming it into an object n2 at the skin membrane, and in the last step of the configuration, it will be sent out to the environment as an object no . It is important to take into account that, in the affirmative case, object δnp+3 is consumed, and since only one object of this kind exists, objects n1 will not have any objects to react with. This stage takes exactly three computational steps, both in the affirmative case and in the negative case. In Figure 1, a graphical description of this process is provided to clarify how this stage works. Axioms 2021,10, 327 9 of 12 C2np+5 C2np+6 C2np+7 C2np+8 C2np+9 C2np+10 np +1 np +1 αp+1 np +2 α0 np +2 δ0 np+1 np +1 np +1 np +1 np +1 α0 np +2 y1 np +2 np +2 np +2 δnp+3 y2 yes np +1 np +1 np +1 np +1 np +2 n1 np +2 np +2 np +2 δnp+3n1 n2 no Figure 1. Evolution of the final stage in the affirmative case (left) and in the negative case (right).