Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors
Year:2010
Research Areas
  • Information technology and adata processing
Information
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.
International
Si
JCR
Si
Title
THEORY OF COMPUTING SYSTEMS
ISBN
1432-4350
Impact factor JCR
0,726
Impact info
Volume
46
Journal number
2
From page
174
To page
192
Month
ENERO
Ranking
Participants
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Computación Natural
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)