A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors

DOI10.1007/s00224-008-9124-zzbMath1209.68264OpenAlexW1981914472MaRDI QIDQ970101

Mario J. Pérez-Jiménez, Victor Mitrana, Maurice Margenstern, Florin Manea

Publication date: 10 May 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://idus.us.es/handle//11441/69142

zbMATH Keywords

Turing machineevolution strategiesnetwork of evolutionary processorscomputational complexity classesevolutionary processor

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Simulating polarization by random context filters in networks of evolutionary processors ⋮ P systems with proteins on membranes characterize PSPACE ⋮ Networks of polarized evolutionary processors ⋮ On the computational power of networks of polarized evolutionary processors ⋮ Filters defined by random contexts versus polarization in networks of evolutionary processors ⋮ Accepting networks of evolutionary processors with subregular filters ⋮ The role of evolutionary operations in accepting hybrid networks of evolutionary processors ⋮ Complexity results for deciding networks of evolutionary processors ⋮ Networks of splicing processors with evaluation sets as optimization problems solvers ⋮ FILTER POSITION IN NETWORKS OF SUBSTITUTION PROCESSORS DOES NOT MATTER ⋮ Polarization: a new communication protocol in networks of bio-inspired processors ⋮ A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors ⋮ Deciding According to the Shortest Computations ⋮ Accepting Networks of Non-inserting Evolutionary Processors

Cites Work

• Networks of evolutionary processors
• Evolutionary systems: A language generating device inspired by evolving communities of cells
• On the size complexity of hybrid networks of evolutionary processors
• Hybrid networks of evolutionary processors are computationally complete
• On the Computational Complexity of Algorithms
• Machines, Computations, and Universality
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item