Home › Biblio

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

Mon, 10/20/2008 - 12:55 — mmartinez
TitleA New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors
Publication TypeJournal Papers
Year of Publication2010
AuthorsManea, F., Margenstern M., Mitrana V., & Pérez-Jiménez M. J.
Journal TitleTheory of Computing Systems
PublisherSpringer New York
Volume46
Pages174-192
Date Published02/2010
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.
KeywordsEvolution strategies; Evolutionary processor; Network of evolutionary processors; Turing machine; Computational complexity classes
URLhttp://www.springerlink.com/content/865688637337gu63/
Notes

online version (http://dx.doi.org/10.1007/s00224-008-9124-z)
Issue2
Impact Factor

0.600
Ranking

133/279 - Q2
ISSN Number1432-4350
DOI10.1007/s00224-008-9124-z