All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size

DOI10.1016/J.IPL.2007.03.001MaRDI QIDQ2379954zbMATH OpenOpenAlexFDO

Authors Florin Manea, Victor Mitrana

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.03.001

zbMATH Keywords

evolutionary processorformal languagesNP-languagetheory of computationTuring machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• DNA Computing
• scientific article; zbMATH DE number 1728707
• Networks of evolutionary processors
• A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors
• On the size complexity of hybrid networks of evolutionary processors

Cites work

• Accepting networks of splicing processors: complexity results
• Aspects of Molecular Computing
• DNA Computing
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Hybrid networks of evolutionary processors are computationally complete
• Introduction to evolutionary computing
• Machines, Computations, and Universality
• On the size complexity of universal accepting hybrid networks of evolutionary processors

Cited in

(12)

• On small, reduced, and fast universal accepting networks of splicing processors
• Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors
• Simulating polarization by random context filters in networks of evolutionary processors
• On the size of computationally complete hybrid networks of evolutionary processors
• ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS
• On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes
• Accepting Networks of Non-inserting Evolutionary Processors
• Universality of SNQ P systems using one type of spikes and restrictive rule application
• All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size
• The role of evolutionary operations in accepting hybrid networks of evolutionary processors
• Accepting networks of genetic processors are computationally complete
• Small universal accepting hybrid networks of evolutionary processors

This page was built for publication: All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size

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