Repositorio de producción científica de la Universidad de Sevilla

A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors

 

Advanced Search
 
Opened Access A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors
Cites

Show item statistics
Icon
Export to
Author: Manea, Florin
Margenstern, Maurice
Mitrana, Víctor
Pérez Jiménez, Mario de Jesús
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2010
Published in: Theory of Computing Systems, 46 (2), 174-192.
Document type: Article
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.
Cite: 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.
Size: 597.4Kb
Format: PDF

URI: https://hdl.handle.net/11441/69142

DOI: 10.1007/s00224-008-9124-z

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)