Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors
Año:2010
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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.
Internacional
Si
JCR del ISI
Si
Título de la revista
THEORY OF COMPUTING SYSTEMS
ISSN
1432-4350
Factor de impacto JCR
0,726
Información de impacto
Volumen
46
DOI
Número de revista
2
Desde la página
174
Hasta la página
192
Mes
ENERO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Computación Natural
S2i 2021 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)