dc.creator | Manea, Florin | es |
dc.creator | Margenstern, Maurice | es |
dc.creator | Mitrana, Víctor | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2018-01-18T09:53:12Z | |
dc.date.available | 2018-01-18T09:53:12Z | |
dc.date.issued | 2010 | |
dc.identifier.citation | Manea, F., Margenstern, M., Mitrana, V. y Pérez Jiménez, M.d.J. (2010). A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors. Theory of Computing Systems, 46 (2), 174-192. | |
dc.identifier.issn | 1432-4350 | es |
dc.identifier.uri | https://hdl.handle.net/11441/69142 | |
dc.description.abstract | We consider three complexity classes defined on Accepting Hybrid Networks
of Evolutionary Processors (AHNEP) and compare them with the classical
complexity classes defined on the standard computing model of Turing machine. By
definition, AHNEPs are deterministic. We prove that the classical complexity class
NP equals the family of languages decided by AHNEPs in polynomial time. A language
is in P if and only if it is decided by an AHNEP in polynomial time and space.
We also show that PSPACE equals the family of languages decided by AHNEPs in
polynomial length. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | Theory of Computing Systems, 46 (2), 174-192. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Evolution strategies | es |
dc.subject | Evolutionary processor | es |
dc.subject | Network of evolutionary processors | es |
dc.subject | Turing machine | es |
dc.subject | Computational complexity classes | es |
dc.title | A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
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.publisherversion | https://link.springer.com/article/10.1007%2Fs00224-008-9124-z | es |
dc.identifier.doi | 10.1007/s00224-008-9124-z | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 19 | es |
dc.journaltitle | Theory of Computing Systems | es |
dc.publication.volumen | 46 | es |
dc.publication.issue | 2 | es |
dc.publication.initialPage | 174 | es |
dc.publication.endPage | 192 | es |
dc.identifier.sisius | 6611217 | es |