Talk:Computational complexity in P systems
Reviewer A
This article provides a complete and at the same time understandable overview of the study of computational complexity in P systems. Nevertheless, the article would benefit from a careful rewording of some sentences and the addition, if possible, of some figures and examples to illustrate the definitions.
Section 1
I propose the following rewording for the first two paragraphs in the section for recognizer P systems in order to avoid words like "usually".
Decision problems, yes-or-no answer problems, are one of the major research topics in complexity theory. Formally, a decision problem, X, is defined as a pair (I_{X},\theta_{X}) such that I_{X} is a language over a finite alphabet (whose elements are called instances) and \theta_{X} is a total boolean function over I_{X}. A language, L_X, is naturally associated to every decision problem, X, as the set of instances for which a positive answer is provided, L_X=\{w \in I_X: \ \theta_X(w)=1\}).
I would reword the last point in the definition of recognizer P system as follows:
(c) in the last step of every computation of the system and never in any previous step, either the object yes or the object no (but not both) must have been sent to the output region of the system
Section 1.1
I propose the next change in the first paragraph of uniform families of P systems in order to avoid words like "at the same time".
In contrast, P systems, likewise logic circuits, are computing devices of finite size that can be described with a fixed amount of initial resources (number of membranes, objects, gates, etc.). According to this, in order to solve a decision problem a (possibly infinite) family of P systems needs to be considered.
In the next two paragraphs of this section there is no definition or description of what a P system with input membrane is. A few lines about this would make the article easier to follow.
Section 1.2
The definition of confluent P systems could be clearer if a figure similar to the one appearing in several papers is included here if possible.
Section 2
There is a typo in the definition of PMC_R. There is an opening begin{itemize} without the closing end{itemize}.
Section 3
I would reword the first sentence as follows:
A basic transition P system is a restricted variant only containing evolution, communication, and dissolution rules. Consequently, these systems are unable to increase the size of the membrane structure.
In the last sentence of this section a citation to the Milano theorem would contribute to the completeness of the article.
Section 4
Problems when formatting using emph.
There seems to be some missing text at the end of the article when discussing some results related to Paun's conjecture.
"Reviewer B"
As a general comment, some examples and figures would be welcome in order to help non-expert readers. Moreover, the last section is not complete. Maybe some part disappeared, or a mistake with a cut-and-paste operation occurred. Finally, I think the result stating that P systems with active membranes but without dissolution rules can be simulated by Deterministic Turing machines in polynomial time should also be added.
Some more specific comments
1. Check some latex command that are not converted. For example, in the following paragraph there are various \emph command, appearing as a text.
The first efficient solutions to NP–complete problems by using P systems with active membranes were given in a semi–uniform way (where the P systems of the family depend on the syntactic structure of the instance) by S.N. Krishna et al. (\emph{Hamiltonian Path}, \emph{Vertex Cover}, 1999), A. Obtulowicz (\emph{SAT}, 2001), Gh. Paun (\emph{SAT}, 2000 and 2001), and C. Zandron et al. (\emph{SAT}, \emph{Undirected Hamiltonian Path}, 2000).
Check also in other part of the contribution for the same problem.
2. When discussing uniformity, some references to the work of Niall and Woods about uniformity below P should be mentioned.
