1. ON A PARTIAL AFFIRMATIVE ANSWER FOR A PĂUN'S CONJECTURE.
- Author
-
PÉREZ-HURTADO, IGNACIO, PÉREZ-JIMÉNEZ, MARIO J., RISCOS-NÚÑEZ, AGUSTÍN, GUTIÉRREZ-NARANJO, MIGUEL A., RIUS-FONT, MIQUEL, and Mitrana, Victor
- Subjects
COMPUTER systems ,BIOLOGICAL membranes ,COMPUTERS in biology ,BIOLOGICAL evolution ,PROBLEM solving ,COMPUTATIONAL complexity ,PROOF theory - Abstract
At the beginning of 2005, Gheorghe Păun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for elementary membranes), polarizations cannot be avoided in order to solve computationally hard problems efficiently (assuming that P ≠ NP). At the middle of 2005, a partial positive answer was given, proving that the conjecture holds if dissolution rules are forbidden. In this paper we give a detailed and complete proof of this result modifying slightly the notion of dependency graph associated with recognizer P systems. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF