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

DOI10.1007/S00224-008-9124-ZMaRDI QIDQ970101zbMATH OpenOpenAlexFDO

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

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

evolution strategiesTuring machinenetwork 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)

Recommendations

• On the size complexity of universal accepting hybrid networks of evolutionary processors
• A survey on computationally complete accepting and generating networks of evolutionary processors
• On the size complexity of hybrid networks of evolutionary processors
• ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS
• On the size of computationally complete hybrid networks of evolutionary processors
• scientific article; zbMATH DE number 1728707
• On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes
• On the power of accepting networks of evolutionary processors with special topologies and random context filters
• Complexity results for deciding networks of evolutionary processors
• The role of evolutionary operations in accepting hybrid networks of evolutionary processors

Cites work

• scientific article; zbMATH DE number 1728707 (Why is no real title available?)
• scientific article; zbMATH DE number 2013489 (Why is no real title available?)
• scientific article; zbMATH DE number 1860699 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Evolutionary systems: A language generating device inspired by evolving communities of cells
• Hybrid networks of evolutionary processors are computationally complete
• Machines, Computations, and Universality
• Networks of evolutionary processors
• On the Computational Complexity of Algorithms
• On the size complexity of hybrid networks of evolutionary processors

Cited in

(15)

• Complexity results for deciding networks of evolutionary processors
• Accepting networks of evolutionary processors with subregular filters
• Polarization: a new communication protocol in networks of bio-inspired processors
• Filters defined by random contexts versus polarization in networks of evolutionary processors
• Simulating polarization by random context filters in networks of evolutionary processors
• The role of evolutionary operations in accepting hybrid networks of evolutionary processors
• A linear time solution for \(N\)-queens problem using generalized networks of evolutionary polarized processors
• P systems with proteins on membranes characterize PSPACE
• Networks of polarized evolutionary processors
• Deciding according to the shortest computations
• All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size
• Networks of splicing processors with evaluation sets as optimization problems solvers
• Accepting Networks of Non-inserting Evolutionary Processors
• Filter position in networks of substitution processors does not matter
• On the computational power of networks of polarized evolutionary processors

This page was built for publication: A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q970101)