dc.creator | Orellana Martín, David | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.date.accessioned | 2021-07-23T10:14:47Z | |
dc.date.available | 2021-07-23T10:14:47Z | |
dc.date.issued | 2020 | |
dc.identifier.citation | Orellana Martín, D. y Riscos Núñez, A. (2020). Seeking computational efficiency boundaries: the Păun’s conjecture. Journal of Membrane Computing, 2 (4), 323-331. | |
dc.identifier.issn | 2523-8906 | es |
dc.identifier.uri | https://hdl.handle.net/11441/116418 | |
dc.description.abstract | In 2005, Gh. Păun raised an interesting question concerning the role of electrical charges in P systems with active
membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of
polarization-less P systems with dissolution rules and division rules only for elementary membranes. Several
approaches have been carried out, and some partial answers have been given. This is probably the most important open
problem in computational complexity theory in the framework of Membrane Computing. The study of the efficiency of
membrane systems has been a very fruitful area, providing not only the above-stated partial answers, but also several
frontiers of efficiency to tackle the P vs NP problem. In this work, a survey on classical and current results on complexity
aspects is given, emphasizing on the frontiers of efficiency and the ingredients taken into account for each of them. | es |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP) | es |
dc.format | application/pdf | es |
dc.format.extent | 9 | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | Journal of Membrane Computing, 2 (4), 323-331. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Păun’s conjecture | es |
dc.subject | Membrane Computing | es |
dc.subject | Computational complexity theory | es |
dc.subject | P systems | es |
dc.title | Seeking computational efficiency boundaries: the Păun’s conjecture | es |
dc.type | info:eu-repo/semantics/article | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | TIN2017-89842-P (MABICAP) | es |
dc.relation.publisherversion | https://link.springer.com/article/10.1007/s41965-020-00058-8 | es |
dc.identifier.doi | 10.1007/s41965-020-00058-8 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
dc.journaltitle | Journal of Membrane Computing | es |
dc.publication.volumen | 2 | es |
dc.publication.issue | 4 | es |
dc.publication.initialPage | 323 | es |
dc.publication.endPage | 331 | es |
dc.contributor.funder | Ministerio de Economia, Industria y Competitividad (MINECO). España | es |